Dynamic Programming

Course Syllabus

Click here to get a copy of the syllabus in postscript format.

Course Objective

Office Hours

Thursdays, 5:00pm-6:00pm
SOM 3.201

TAs

To be announced.

Text

Introduction to Stochastic Dynamic Programming, by Sheldon M. Ross. Academic Press, New York, 1983.

Prerequisites

OPRE 6331; or consent of the instructor.

Grading Scheme

Presentation: l00%

Course Outline

Chapters 1-5, 7, and research papers. Specific topics are:
  1. Finite-Stage Examples
  2. Discounted Dynamic Programming
  3. Negative Dynamic Programming - Minimizing Costs
  4. Positive Dynamic Programming - Maximizing Rewards
  5. Average Reward Criterion
  6. Linear-Programming Formulations
  7. Bandit Processes

Papers Suggested for Presentation

  1. Stidham, S., Jr., and Weber, R. [1989]. "Monotonic and Insensitive Optimal Policies for Control of Queues with Undiscounted Costs." Operations Research, 37, pp. 611-625.
  2. Sennott, L. I. [1993]. "The Average Cost Optimality Equation and Critical Number Policies." Probability in the Engineering and Informational Sciences, 7, pp. 47-68.
  3. Subelman, E. J. [1979]. "The Dependence of Betting Strategies on the Probability of Winning." Journal of Applied Probability, 16, pp. 855-866.
  4. Righter, R. [1990]. "Stochastically Maximizing the Number of Successes in a Sequential Assignment Problem." Journal of Applied Probability, 27, pp. 351-364.
  5. Righter, R. [1989]. "A Resource Allocation Problem in a Random Environment." Operations Research, 37, pp. 329-338.
  6. Nawijn, W. M. [1985]. "The Optimal Look-Ahead Policy for Admission to a Single-Server System." Operations Research, 33, pp. 625-643.
  7. Nawijn, W. M. [1990]. "Look-Ahead Policies for Admission to a Single-Server Loss System." Operations Research, 38, pp. 854-862.
  8. Tamaki, M. [1991]. "A Secretary Problem with Uncertain Employment and Best Choice of Available Candidates." Operations Research, 39, pp. 274-284.
  9. Tamaki, M. [1991]. "A Full-Information Best-Choice Problem with Finite Memory." Journal of Applied Probability, 23, pp. 718-735.
  10. Sennott, L. I. [1991]. "Constrained Discounted Markov Decision Chains." Probability in the Engineering and Informational Sciences, 5, pp. 463-475.
  11. Hopp, W. J., Bean, J. C., and Smith, R. L. [1988]. "A New Optimality Criterion for Non-Homogeneous Markov Decision Processes." Operations Research, 35, pp. 875-883.
  12. Monahan, G. E. [1982]. "A Survey of Partially Observable Markov Decision Processes: Theory, Models, and Algorithms." Management Science, 28, pp. 1-16.
  13. Assaf, D., and Levikson, B. [1991]. "Optimal Advertising Policy for Selling a Single Asset." Probability in the Engineering and Informational Sciences, 5, pp. 89-100.
  14. Xu, S. H., Righter, R., and Shanthikumar, J. G. [1992]. "Optimal Dynamic Assignment of Customers to Heterogeneous Servers in Parallel." Operations Research, 40, pp. 1126-1138.
  15. Song, J.-S., and Zipkin, P. [1993]. "Inventory Control in a Fluctuating Demand Environment." Operations Research, 41, pp. 351-370.
  16. Gallego, G., and van Ryzin, G. [1994]. "Optimal Dynamic Pricing of Inventories with Stochastic Demand over Finite Horizons." Management Science, 40, pp. 999-1020.
  17. Higle, J. L., Bean, J. C., and Smith, R. L. [1990]. "Deterministic Equivalence in Stochastic Infinite Horizon Problems." Mathematics of Operations Research, 15, pp. 396-407. Bean, J. C., Higle, J. L., and Smith, R. L. [1992]. "Capacity Expansion under Stochastic Demands." Operations Research, 40, Supp. No. 2, pp. 210-216.
  18. Kapuscinski, R., and Tayur, S. [1998]. "A Capacitated Production-Inventory Model with Periodic Demand." Operations Research, 46, pp. 899-911.
  19. Angelus, A., and Porteus, E. L. [2002]. "Simultaneous Capacity and Production Management of Short-Life-Cycle, Produce-to-Stock Goods under Stochastic Demand." Management Science, 48, pp. 399-413.
  20. Wu, R., and Fu, M. C. [2003]. "Optimal Exercise Policies and Simulation-Based Valuation for American-Asian Options." Operations Research, 51, pp. 52-66. Ben-Ameur, H., Breton, M., and L'Ecuyer, P. [2002]. "A Dynamic Programming Procedure for Pricing American-Style Asian Options." Management Science, 48, pp. 625-643.
  21. Feng, Y., and Xiao, B. [2001]. "A Dynamic Airline Seat Inventory Control Model and Its Optimal Policy." Operations Research, 49, pp. 938-949.
  22. Smith, J. E., and McCardle, K. F. [2002]. "Structural Properties of Stochastic Dynamic Programs." Operations Research, 50, pp. 796-809.
  23. Whittle, P. [1981]. "Arm Acquiring Bandits." Annals of Probability, 9, pp. 284-292.
  24. McCardle, K. F. [1985]. "Information Acquisition and the Adoption of New Technology." Management Science, 31, pp. 1372-1389.
  25. Cheevaprawatdomrong, T., and Smith, R. L. [2004]. "Infinite Horizon Production Scheduling in Time-Varying Systems under Stochastic Demand." Operations Research, 52, pp. 105-115.

Assignments