Return to Index
Operations Research Models and Methods
Models Section
Teach Dynamic Programming Add-in

The Teach Dynamic Programming Add-in provides a tool for constructing and solving general discrete dynamic programming problems. When installed, the menu items on the left are added to the Teach menu. The Model command gives access to a number of built-in models for well known problems. The General command allows the student to construct a general DP structure. Since DP allows a very large class of problems, this option can be useful for the student or practitioner with experience in building Excel expressions.

The Options command controls the solution method, the degree of student interaction in the solution process and the detail of the output display. The Relink Buttons command is necessary when opening models constructed on a different computer. Model pages contain buttons that will generate a message from Excel concerning links. Cancel that message and then choose the Relink Buttons command to create buttons that work.


Dynamic programming (DP) has quite a different model form than the other types of mathematical programming. Instead of an objective function and constraints, dynamic programming models consist of a collection of equations that describe a sequential decision process.

The process begins in some initial state, the first decision moves it to a second state, and then continues through alternating decisions and states until a final state is reached. For a given problem, the model must provide:

  • mathematical vectors that describe states and decisions
  • initial and final state definitions
  • transition functions that map the current state and decision to the next state in the sequence
  • the objective function that evaluates the sequence of decisions

Many problems are naturally described as a sequential decision process and are ready candidates for a DP solution. Others that seem more naturally stated as Integer Programming models can be adapted to the DP format. DP has an advantage over other formulations in that it does not require linearity.

One difficulty with DP is the curse of dimensionality. DP solves for the optimal solution from every feasible state. If the number of feasible states is too large, a very long time might be required to solve a problem.

This DP add-in provides a general structure with which most problems appropriate for DP can be modeled and solved.

Use the links at the left to reach other relevant links on this site. The DP Models PDF describes the general model structure as well as several additional problem classes with their dynamic programming models. The DP Methods PDF describes the methods used for solution. The Models section has a more mathematical treatment of the investment problem used as an example in this section. The Download links download the Excel add-in and the Excel demo file for this section. Be sure you know how to install and use add-ins before attempting to use these files.


Return to Top

tree roots

Operations Research Models and Methods
by Paul A. Jensen
Copyright 2004 - All rights reserved