Powell-WSC Tutorial - ADP for high dimensional resource allocation July12007

Proceedings of the 2007 Winter Simulation ConferenceS. G. Henderson, B. Biller, M. H. Hsieh, J. Shortle, J. D. Tew, and R. R. Barton, eds.Approximate Dynamic Programming for High Dimensional ProblemsWarren B. PowellDepartment of Operations Research and Financial EngineeringPrinceton UniversityPrinceton, NJ 08544, U.S.A.ABSTRACT The “simulation” of activities in the future is handled bythe optimization algorithm.There is a wide range of simulation problems that involve These problems have created a tension over the yearsmaking decisions during the simulation, where we would between the simulation community, which promotes itsliketomakethebestdecisionspossible, takingintoaccount ability to not only handle uncertainty but also a varietynotonlywhatweknowwhenwemakethedecision,butalso of complex operational considerations, and optimization,the impact of the decision on the future. Such problems whichfocusesonitsabilitytoproducehighqualitysolutions.can be formulated as dynamic programs, stochastic pro Acommonstrategyistosimulateanoptimizationproblembygrams and optimal control problems, but these techniques steppingforwardintime, solvingsequencesofoptimizationrarely produce computationally tractable algorithms. We problems based on what is known at a point in time. Atdemonstrate how the framework of approximate dynamic time t, we can solve an optimization problem using onlyprogramming can produce near optimal (in some cases) or what is known at timet, or using ...