Chapter 7

Teaching Dynamic Programming and Duality Insights Using Games, Interdiction, and Robust Optimization

J. Cole Smith

Department of Industrial and Systems Engineering, University of Florida, Gainesville, Florida 32611, cole@ise.ufl.edu

Abstract

This tutorial discusses two aspects in operations research foundations that have often proven formidable to beginning students: dynamic programming and duality. Although mathematically inclined students may immediately pick up on these very elegant and powerful concepts, the intuition behind these ideas is often unusual and confusing to beginners. This tutorial begins by discussing an effective method for teaching dynamic programming concepts to undergraduate students in an entertaining and accessible manner. This background permits an application-oriented discussion of duality, which can in turn be used to teach emerging topics in interdiction and robust optimization. These topics allow one to touch upon some of the nuances of linear programming duality concepts, such as left- and right-hand shadow prices. The integrated manner in which these topics are presented may allow students to learn the concepts in a more coherent manner and better understand the scope and limitations of modern mathematical programming approaches.

Key words: dynamic programming; duality; interdiction; robust optimization; shortest path

The 2012 volume of the TutORials in Operations Research series will be available to people who have registered for the 2012 INFORMS Annual Meeting. All INFORMS members will be able to access TutORials after January 1, 2013. Printed TutORials books from this and previous years can also be ordered here, along with CDs from 2005 to 2009.

Download Chapter 7 - Password-protected content.

For login instructions click here.

________________________________________________

Citation information:

Smith, C. Teaching Dynamic Programming and Duality Insights Using Games, Interdiction, and Robust Optimization. P. Mirchandani, ed. INFORMS TutORials in Operations Research, Vol. 9. INFORMS, Hanover, MD, pp. 127--150.

http://dx.doi.org/10.1287/educ.1120.0098