This section contains a series of tutorial articles and book chapters. Often, these are an easy place to start. Journal articles can be quite technical, and they also represent our first attempt to write up a piece of research. These book chapters synthesize a lot of our research, and they are intended to be more tutorial in style.
W. B. Powell, H. Simao, B. Bouzaiene-Ayari, “Approximate Dynamic Programming in Transportation and Logistics: A Unified Framework,” European J. on Transportation and Logistics, Vol. 1, No. 3, pp. 237-284 (2012). DOI 10.1007/s13676-012-0015-8.
Using the contextual domain of transportation and logistics, this paper describes the fundamentals of how to model sequential decision processes (dynamic programs), and outlines four classes of policies. A section describes the linkage between stochastic search and dynamic programming, and then provides a step by step linkage from classical statement of Bellman’s equation to stochastic programming. The remainder of the paper uses a variety of applications from transportation and logistics to illustrate the four classes of policies.
(Click here to download paper)
W. B. Powell, I. O. Ryzhov, “Optimal Learning and Approximate Dynamic Programming,” Reinforcement Learning and Approximate Dynamic Programming for Feedback Control, (F. Lewis and D. Liu, eds.), John Wiley/CRC Press, New York, pp. 410-431, 2013.
This chapter covers methods for solving the exploration vs. exploitation problem from two perspectives: policy search (a dynamic program with a pure belief state), and dynamic programming with a physical state. After providing an overview of some of the most popular heuristics, we describe how the knowledge gradient can be used in both settings. The knowledge gradient is illustrated for both offline and online learning, both for policy search and in dynamic programming with a physical state.
(Click here to download paper)
Powell, W. B., “The knowledge gradient for optimal learning,” Encyclopedia of Operations Research and Management Science, John Wiley and Sons. (to appear)
This is a short introduction to the concept of the knowledge gradient for optimal learning, including both online and offline applications.
(click here to download paper)
Powell, W. B., “Approximate Dynamic Programming I: Modeling,” Encyclopedia of Operations Research and Management Science, John Wiley and Sons. (to appear)
With apologies, this chapter has nothing to do with approximate dynamic programming. I have found that before you solve a problem with ADP (or any other strategy), you should model your problem properly. This article outlines the classical framework used in control theory (less familiar to people in operations research), that is very friendly to simulation-based models. Of particular interest (at least to me) is section 4, which describes nine types of policies – one of these uses approximate dynamic programming.
(click here to download: ADP – I: Modeling)
Powell, W. B., “Approximate Dynamic Programming II: Algorithms,” Encyclopedia of Operations Research and Management Science, John Wiley and Sons.
This is a brief introduction to approximate dynamic programming. Think of it as just a taste.
(click here to download: ADP – II: Algorithms)
Powell, W. B. “What you should know about approximate dynamic programming,” Naval Research Logistics, Vol. 56, No. 3, pp. 239-249, 2009.
This article is a brief overview and introduction to approximate dynamic programming, with a bias toward operations research. It highlights the major dimensions of an ADP algorithm, some strategies for approximating value functions, and brief discussions of good (and bad) modeling and algorithmic strategies.
(click here to download paper)
Powell, W.B., “Approximate Dynamic Programming: Lessons from the field,” Proceedings of the Winter Simulation Conference, December, 2008.
This is the third in a series of tutorials given at the Winter Simulation Conference. This one has additional practical insights for people who need to implement ADP and get it working on practical applications.
(Click here to download paper)
Powell, W. B. and P. Frazier, “Optimal Learning,” TutORials in Operations Research, Chapter 10, pp. 213-246, Informs (2008).
This was an invited tutorial on the topic of optimal learning, and represents a fairly easy introduction to the general field of information collection. Although the page constraints limited the scope, it covers the central dimensions of information collection, along with an overview of a number of the most popular heuristic policies. Of course, we include an introduction to the knowledge gradient concept.
(click here to download paper)
Powell, W. B., “Approximate Dynamic Programming – A Melting Pot of Methods,” Informs Computing Society Newsletter, Fall, 2008 (Harvey Greenberg, ed.)
This article appeared in the Informs Computing Society Newsletter. It provides an easy, high-level overview of ADP, emphasizing the perspective that ADP is much more than an algorithm – it is really an umbrella for a wide range of solution procedures which retain, at their core, the need to approximate the value of being in a state.
(click here to download paper)
Powell, W.B., “Real-time dispatching for truckload motor carriers,” in Logistics Engineering Handbook (G. Don Taylor, ed.), CRC Press, 2007, pp. 15-1 – 15-30. (c) CRC Press.
This paper describes our experience implementing a real-time optimization model at Burlington Motor Carriers. Intended for a broad audience, it describes the basics of the model and some of tbe behind-the-scenes events that were encountered during implementation.
(click here to download paper)
Powell, W.B., A. George, B. Bouzaiene-Ayari and H. Simao, “Approximate Dynamic Programming for High Dimensional Resource Allocation Problems,” Proceedings of the IJCNN, Montreal, August 2005.
This is an easy introduction to the use of approximate dynamic programming for resource allocation problems. It shows how math programming and machine learning can be combined to solve dynamic programs with many thousands of dimensions, using techniques that are easily implemented on a laptop.
(Click here to download paper)
Powell, W.B., “Approximate Dynamic Programming for High-Dimensional Problems ,” Proceedings of the Winter Simulation Conference, December, 2007.
This short tutorial article, prepared for the Winter Simulation Conference, presents notation and fundamental algorithmic ideas to solve the types of high-dimensional applications which arise in a broad range of resource allocation problems.
(Click here to download paper)
Powell, W.B., “The Optimizing-Simulator: Merging Simulation and Optimization using Approximate Dynamic Programming,” Proceedings of the Winter Simulation Conference, December, 2005.
Approximate dynamic programming involves iteratively simulating a system. As a result, it often has the appearance of an “optimizing simulator.” This short article, presented at the Winter Simulation Conference, is an easy introduction to this simple idea.
(Click here to download paper)
Powell, W.B. and B. van Roy, “Approximate Dynamic Programming for High Dimensional Resource Allocation Problems,” (in Learning and Approximate Dynamic Programming: Scaling up to the Real World, J. Si, A. Barto, W.B. Powell and D. Wunsch, eds.), John-Wiley and Sons, New York, 2004.
We have done a lot of work that involves solving multistage linear programs for resource allocation using dynamic programming. This relatively short chapter is a quick introduction to this work, and brings together the themes of approximate dynamic programming and linear programming.
(Click here to download paper)
Powell, W.B., B. Bouzaiene-Ayari and H.P. Simao, “Dynamic Models for Freight Transportation,” Handbooks in Operations Research and Management Science: Transportation (G. Laporte and C. Barnhart, eds.), Elsevier, Amsterdam, 2007.
This chapter focuses on modeling the organization and flow of decisions and information in transportation. The chapter describes how to model sequential information and decision processes, and discusses four classes of information and the algorithmic strategies that are associated with each class. Approximate dynamic programming methods are introduced and illustrated for several classes of problems that arise in transportation and logistics.
(Click here to download paper)
Powell, W. B. and H. Topaloglu, “Stochastic Programming in Transportation and Logistics,” Handbooks in Operations Research and Management Science: Stochastic Programming (A. Shapiro and A. Ruszczynski, eds.), Elsevier, Amsterdam, pp. 555-635, 2003..
We introduce adaptive learning algorithms in the context (and notation) of stochastic programming, using fleet management (and particularly freight car distribution) as the illustrative application. The chapter is a good review of different approximation strategies, and uses the freight car distribution problem to illustrate how some problems exhibit separability and how to solve problems that are nonseparable.
(Click here to download paper)
Powell, W.B., “Dynamic Models of Transportation Operations,” Handbooks in Operations Research and Management Science: Supply Chain Management, (S. Graves and T. A. G. de Tok, eds.), Elsevier, Amsterdam, pp. 677-756, 2003.
This chapter provides an overview of problems in freight transportation, and a modeling and algorithmic strategy for solving these problems. For students looking for a single reference that covers the DRTP modeling framework and our approximate dynamic programming strategies, this is a good overview.
(Click here to download paper)
Powell, W.B. and H. Topaloglu, “Fleet Management,” in Applications of Stochastic Programming, (S. Wallace and W. Ziemba, eds.), Math Programming Society – SIAM Series in Optimization, Philadelphia,pp. 185-216, 2005.
Stochastic programming has been steadily making its way into a variety of application areas. This chapter demonstrates the use of a class of stochastic programming methods for fleet management applications, using the freight car distribution problem as a problem context.
Powell, W. B., P. Jaillet and A. Odoni, “Stochastic and Dynamic Networks and Routing,” Handbook in Operations Research and Management Science, Vol. 4, Networks, (M.O. Ball, T.L. Magnanti, C.L. Monma and G.L. Nemhauser, eds.), pp. 141-295, 1995.
The hard part about writing a chapter for a handbook on dynamic models is that the field is very new and evolving quickly. However, this chapter contains a fairly extensive literature review and should serve as a useful reference for research prior to 1993-94.
“Optimization Models and Algorithms: An Emerging Technology for the Motor Carrier Industry,” Special Issue of IEEE on Intelligent Vehicle /Highway Systems, pp. 68 – 80, 1990. (Winner, Best Paper on Land Transportation from IEEE Section on Vehicular Technologies, 1992.)
This is a survey of a variety of optimization strategies for routing and scheduling of vehicles. The best part of this paper was that I received a marriage proposal from an appreciative reader.
“Toward a Unified Framework for Real-Time Logistics Control,” Military Journal of Operations Research, Vol. I, No. 4, Winter, 1996, pp. 69-79.