Warren B. Powell
Department of Operations Research and Financial Engineering
Princeton University
Princeton, NJ 08544
www.castlelab.princeton.edu

Dynamic programming has often been dismissed because of the well-known curse of dimensionality. State variables with as few as five or ten dimensions can produce computationally intractable models. When applied to operational problems such as managing fleets of vehicles, the situation is even worse - there are three curses of dimensionality. In this talk, I will show how the techniques of approximate dynamic programming have allowed us to obtain effective solutions to very large-scale problems that arise in industrial applications. In real projects with railroads, major trucking companies and a business jet operator, we are using approximate dynamic programming to solve problems where the state variable has hundreds of thousands of variables. The goal is not merely to simulate, but to produce solutions that have the behavior of optimizing over time (not just at a point in time). The techniques handle numerous forms of uncertainty in a natural way, but they were originally developed primarily as a decomposition strategy for solving large scale deterministic problems that are too large for commercial solvers. Equally attractive, the methods work well with existing models and algorithms for deterministic problems.