Return to Index
Operations Research Models and Methods
Computation Section
Subunit Dynamic Programming Data

The DP Data add-in constructs tables that describe data for instances of specific application areas of dynamic programming or Markov analysis. The DP Data add-in calls the DP Models add-in to construct the model form to hold the decisions and stochastic features of the model. The DP Data add-in then fills the model form with parameters linked to the data form. The resulting model will ultimately be used to provide data for the DP Solver or Markov Analysis add-ins.

Although the model forms available in the DP Models add-in are very general, it is somewhat difficult for the unskilled user of Excel to build a model. The DP Data add-in removes this difficulty by automatically building the model for specific problem classes. At this time only five classes are available: birth-death, finite queue, random walk, inventory and resource. For each class there are several variations. Future editions of the add-in may include more problem classes.

Addition of new problem classes requires VBA programming. The programs of this add-in are not password protected so you can examine the programs for existing classes. As a user of this add-in, you may find it interesting to add new classes. Several program features make this not too difficult. I am glad to accept contributions of new classes and will include them in future editions. I will also be willing to help aspiring contributors.

The picture to the left shows the menus of the DP Data and DP Models add-ins. To use the DP Data add-in select the Data item from the menu.

The Start and Finish commands are used to respectively add and remove buttons from the worksheets. This is important when moving models from one computer to another. Always delete the buttons with the Finish command before attempting to open a model on another computer. Otherwise you will experience an error message regarding links. Add buttons back with the Start command. Although the Finish command deletes all buttons from the workbook, the Start command only adds buttons for the add-in from which the command was called.


Selecting the Data item will present the dialog at the left. The problem type is selected with a button at the left of the dialog. The model types are select by the buttons on the right. Not all classes have all model types.


The dialog provides four model types. The Deterministic DP (DDP) type has models with only states and actions because the transitions caused by decisions are deterministic. The Stochastic DP type has models with uncertain transitions. We use MDP as an abbreviation because the models are similar to the Markov Decision Process. The Discrete Time Markov Chain (DTMC) and the Continuous Time Markov Chain (CTMC) models have transition events, but no actions. The DTMC considers time in discrete steps and specifies probabilities of transition. The Continuous Time Markov Chain (CTMC) considers time as continuous and specifies rates of transition. All of these model types are considered by the other add-ins in this collection, but here we describe only the data portion.

To analyze CTMC model, the Markov Analysis add-in must also be installed. The analysis of DDP and MDP models requires the DP Solver add-in. The DTMC model may use either the Markov Analysis or DP Solver add-ins.


Clicking the OK button presents a second dialog with data specific to the problem type. The Model Name field accepts a name and is initially filled by a default name. The name may be changed on this dialog, but not after the model is constructed. If you choose a new name, make it with a small number of letters, include no spaces, start the name with a letter, and do not use punctuation. The names "Prob 1" or "Prob.1" will both fail because the first contains a space and the second a period.



Although the add-ins do not restrict the size of the problem entered, some computational methods are impractical for large problems. The size of the worksheet in terms of rows and columns limits some models. Some computations in the DP Solver add-in use the Excel INVERSE function that is limited to about 50 states, although the limit seems to be greater for Excel 2007. The size of a model, as measured by the number of states, decisions, and transitions, is an important feature of a DP model because for many problems these numbers may be very large. In the parlance of dynamic programming this is the curse of dimensionality.

The remainder of this section describes the problem types and their models. For more detailed discussions of the modeling and solutions processes, see the other parts of this DP collection.


Return to Top

tree roots

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

Next Page