Approximate Dynamic Programming for High-Dimensional Resource Allocation Problems

Warren Powell
Department of Operations Research and Financial Engineering
Princeton University


Wednesday, May 2, 2007
4:30 - 5:30 PM
Terman Engineering Center, Room 453


Abstract:

Stochastic resource allocation problems produce dynamic programs with state, information and action variables with thousands or even millions of dimensions, a characteristic we refer to as the "three curses of dimensionality." Classical techniques in approximate dynamic programming solve only part of the problem. We show how the use of the post-decision state variable allows us to break a problem into three distinct components: simulation, deterministic optimization and statistical learning. This strategy decomposes problems over time, allowing us to use commercial packages to solve even large-scale integer programming problems, producing solutions that are optimal at a point in time (given a value function approximation), with approximate (but high quality) solutions over time. The talk will also describe how we have overcome the challenge of estimating value function approximations for complex resource allocation problems, and the critical, but often overlooked, choice of stepsize rule. We summarize the state of what we can prove theoretically, and then demonstrate the power of these methods in the context of several industrial applications.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html