Dynamic Programming Examples - Cab Solution/Alternative Data Forms
 Three different data forms are available for the DP Solver add-in. The states, actions and events are the same for the forms, but the representation of the transition probabilities and costs change. This page shows the three forms for the cab problem. The values on the various lists are for the optimum solution. Although the measure of effectiveness for the cab problem is profit, the discussion uses the more general term cost. Probability/Cost Matrix This format was illustrated on the previous page. It has both transition probabilities and transitions costs entered in the matrix format. The result is below. Notice that each state/action pair has a row in the decision matrix, so the number of rows in the two transition matrices is equal to the number of decisions. The number of columns in the two matrices is equal to the number of states. This option is easiest to use for small problems, but not convenient for very large problems. Also, Excel is limited by the number of columns on a worksheet. With Excel 2003/2004 worksheets have about 256 columns, so the representation is limited to about 100 states. The Next Value and State Probability vectors each have the number of components equal to the number of states. It is convenient for computational purposes to have these vectors located above the transition probability matrix. Probability/No Cost Matrix Option This option deletes the Transition Cost matrix and replaces it with the Expected Transition Cost vector in column AD. The solution methods do not use the individual transition costs, only the expected cost for each state/action pair. Of course, this requires the user to compute the expected values outside of the DP Solver add-in. Considering the number of columns available for Excel 2003/2004, this option allows about 200 states. Transition List Option This option represents transition probabilities and costs with lists rather than matrices. Neither the probability nor cost matrix is used, so the number of columns Excel allows is no longer a limitation. The decision list is modified as shown below. Only the state index and action index are entered by the user. For the current example only the action for decision 6 is different than the default values. The decision indicates that the radio alternative is not available in city B. All the yellow columns contain formulas necessary for the solution methods. The Transition List is placed to the right of the decision list and carries the transition information. Each decision has one or more rows on this list. The Event Index is used to construct the Transition Name. Each transition occupies a row of this matrix with its cost in column AP, its probability in column AQ and the state reached via the transition in column AR. The information describing the Next Value and the State Probability are placed as columns in the state list, rather than above the transition probability matrix. For most problems, the transition format is far more efficient than the matrix format, because often there are few transitions from each state/action combination. Since the number of rows for Excel worksheets is very large, the Transition format allows much larger problems than the matrix formats. Summary All three data formats are available for Markov Chains and Markov Decision Processes. Only the transition list option is available for deterministic dynamic programming.

Operations Research Models and Methods
Internet
by Paul A. Jensen