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

The option command allows access to dialog boxes than change the options for solution, output presentation and user interaction. Selection of the Options item presents the dialog below. The three buttons each have a dialog to set their respective parameters.


Set Strategy


The three solution strategies listed on the dialog are available for solution. The dialog changes the Strategy range on the worksheet. The program runs the solution strategy when the Solve button is pressed.


Set Output


For all selections in the Show Detail frame except None, a worksheet is added with a name like DP1_Details. The prefix to the word Details is the name of the DP worksheet.

The results printed on the Details worksheet depends on the button pressed. In all cases there is a line for each state of the problem. If one expects the problem to have very many states, the option should not be used. As we descend the list of options, more and more output is provided. The state tree is the structure used to store the state information by the computer.


Set Interaction


These options affect the information displayed during a run of the program. Options providing more information are helpful to the student trying to discover the DP solution process.


The Demonstration option presents a dialog at each step of the procedure. The dialog below shows the initial state of the forward generation procedure.


After watching the dialog for several steps, the student may choose to skip to the next major activity of the algorithm without the detailed dialog. The Let Go button accomplishes this. For the case shown, the demonstration would begin again at the forward generation procedure. Other major steps in the computation are the recursive procedure and the recovery procedure.

The buttons at the bottom of the dialog allow a switch in the interaction option. The Run/Stop option runs without interruption for a number of steps equal to the value in the cell at the lower right (100). When that number is reached the process displays the demo dialog. In this way the student can observe the process at a variety of points during the solution process.

The Run/no stop option allows the program to run to completion without interruption. While the program is running the progress strip at the bottom of the Excel screen shows information about the solution. The information is updated at the interval specified as the number of states between stops.

The Update Screen checkbox at the bottom of the dialog controls the display during optimization. If it is not checked, the screen is not updated during the process until the end. This is the fast option and should be the choice for large problems. When the box is checked, the changes in the state and decision vectors may be seen as rapidly varying numbers. The number change too rapidly to be observed, but the result is a dynamic display that gives the user some idea about the procedures of the computer program.

The Show Graphics checkbox causes the solution process to generate a graphical display as illustrated below. The figure illustrates the state space for a knapsack problem with a single constraining resource. The model has two state variables, and for the example the maximum values are 10 for both. The strategy used is forward generation and backward recursion.

The display shows the states as colored circles: red for initial states, white for intermediate feasible states, gray for infeasible states, blue for final states and gold for states along the optimal path. The states are located on a grid defined for S1, the first state variable, and S2, the second state variable. Lines connect the states. Not shown on the figure are narrow black lines which show the change of states for a tentative decision. The red lines show the optimum decision leaving each state, the heavy black lines show the optimum path.

The graphical display is a useful tool for learning the DP process. When both the Demo and graphical options are chosen, each step is explained with a text dialog and a graphic presentation. The graphical option is available only for problems with two state variables. The maximum range for each variable must be no more than 20.



Return to Top

tree roots

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

Next Page