Approximate dynamic programming: Lessons from the field

Approximate dynamic programming is emerging as a powerful tool for certain classes of multistage stochastic, dynamic problems that arise in operations research. It has been applied to a wide range of problems spanning complex financial management problems, dynamic routing and scheduling, machine scheduling, energy management, health resource management, and very large-scale fleet management problems. It offers a modeling framework that is extremely flexible, making it possible to combine the strengths of simulation with the intelligence of optimization. Yet it remains a sometimes frustrating algorithmic strategy which requires considerable intuition into the structure of a problem. There are a number of algorithmic choices that have to be made in the design of a complete ADP algorithm. This tutorial describes the author's experiences with many of these choices in the course of solving a wide range of problems.