Asee peer logo

Framework For Dynamic Programming

Download Paper |

Conference

2006 Annual Conference & Exposition

Location

Chicago, Illinois

Publication Date

June 18, 2006

Start Date

June 18, 2006

End Date

June 21, 2006

ISSN

2153-5965

Conference Session

Issues in Computer Education

Tagged Division

Computers in Education

Page Count

8

Page Numbers

11.649.1 - 11.649.8

Permanent URL

https://peer.asee.org/562

Download Count

93

Request a correction

Paper Authors

biography

Louis Plebani Lehigh University

visit author page

Dr. Plebani, P.E., is a faculty member in the Department of Industrial and Systems Engineering at Lehigh University where he teaches Dynamic Programming.

visit author page

Download Paper |

Abstract
NOTE: The first page of text has been automatically extracted and included below in lieu of an abstract

Framework for Dynamic Programming

Abstract

Dynamic programming (DP) is a versatile technique for modeling and solving sequential optimization problems. While the approach is well known to the Operations Research community, its impact has been limited when compared to other mathematical programming techniques such as linear programming. Ironically, in part, this has been due to its flexibility. Because DP can be adapted to a myriad of problems and those models can be implemented in a variety of ways, many modelers, particulary inexperienced ones, are overwhelmed by the large number of choices. This is often referred to as the “art” of dynamic programming. Our goal was to provide a framework and base computer code for students to achieve an ease of modeling and solution for dynamic programming similar to what has been achieved for linear programming. In so far as the teaching dynamic programming, this will allow educators in operations research to focus their teaching on issues relevant to dynamic programming as opposed to computer programming issues; and allow students in operations research to focus their learning on the power of dynamic programming, as opposed to the nuances of computer implementations.

Introduction

Since the formulation of Dynamic programming (DP) by Bellman,1 it has been successfully applied to a variety of problems, including capacity planning, equipment replacement, production planning, production control, assembly line balancing and capital budgeting (hundreds of articles referring to the use of dynamic programming are given in Sniedovich and Cole7 ). Despite seemingly successful, dynamic programming has not been adapted nearly as readily, and thus successfully, as its mathematical programming counterparts such as linear and integer programming. Some of the reasons for this are the lack of standardization in representing dynamic programs and the lack of available software to aid implementation. Our work in developing a standardized framework is an attempt to address these shortcomings.

Dynamic programming can be defined as follows: At each stage in a process, a decision is made given the state of the system. Based on the state, decision and possibly the stage, a reward is received or a cost is incurred and the system transforms to another state where the process is repeated at the next stage. Note that this transformation can be either deterministic, where the resulting state is known with certainty, or stochastic, where a number of resulting states can occur with known probability. The idea of transforming or moving between states in time captures the concept of a sequential decision process as one evaluates decisions at each state in time and determines the optimal decision. The goal is to find the optimal policy, which is the best decision for each state of the system, or at least the optimal decision for the initial state of the system. It is the definition of a system according to states that makes dynamic programming so appealing, as it can model nearly any type of system.

Unfortunately, this flexibility generally requires some sophistication on the part of the user in model development. For example, a simple finite-horizon equipment replacement

Plebani, L. (2006, June), Framework For Dynamic Programming Paper presented at 2006 Annual Conference & Exposition, Chicago, Illinois. https://peer.asee.org/562

ASEE holds the copyright on this document. It may be read by the public free of charge. Authors may archive their work on personal websites or in institutional repositories with the following citation: © 2006 American Society for Engineering Education. Other scholars may excerpt or quote from these materials with the same citation. When excerpting or quoting from Conference Proceedings, authors should, in addition to noting the ASEE copyright, list all the original authors and their institutions and name the host city of the conference. - Last updated April 1, 2015