Return to Index
Operations Research Models and Methods
Computation Section
Subunit Dynamic Programming Examples
 - Baseball Solution

The solution of a DP model is found with the DP Solver add-in (dp_solver.xla). This program can be run independently, but the easiest way to use it is to construct a model with the DP Models add-in and call the DP Solver from the model page. Click the Transfer to DP Solver at the top of the model page.


Three kinds of DP Solver models are available. The first, Transition List, presents the data much like the lists constructed by the DP Models add-in. All transition information is described by lists. The number of transitions determines the number of rows in the Solver model. Excel allows very many worksheet rows.

The second option, Probability/Cost Matrix, shows the transition probabilities and costs as matrices. The dimensions of the two matrices are (number of decisions)x(number of states). For small problems this is the most visual representation. For larger problems, the problem size is limited by the number Excel columns. With older versions of Excel the number of columns restricts the use of this representation to about 100 states. Excel 2007 allows many more worksheet columns than Excel 2003, thus increasing the problem size. Viewing the transition matrix is not very useful for large problems because the nonzero transitions are usually a very small proportion of the total number of matrix entries.

The third format, Probability/No Cost Matrix, shows the transition probabilities as a matrix, but computes the expected transition cost and shows that result in a single column. Models of this form are limited to about 200 states.

For this example we use the Transition List option. The same DP model can provide the data for several Solver worksheets by entering different names in the name field.

  The DP Solver model has much the same appearance as the lists created by the DP Models add-in. The primary differences are columns created for computation of solutions. Data is simply copied from the lists rather than linked through formulas. If the model changes the DP Solver form must be rebuilt. The user need not interact with DP Solver form. All equations are automatically inserted and solutions are obtained by clicking Solve button at the top of the worksheet.



The DP Solver model is placed on a new worksheet called BB_DP. Parameters are placed at the upper left corner of the worksheets. Yellow cells hold parameters that should not be changed. The green cells hold information about the current DP solution technique employed. Important to this discussion are the two cells labeled Maximum Value Difference and Sum Probability Difference. The values in these cells should converge to zero as the algorithm progresses.




  Columns D through J hold data for the states of the model. The yellow cells in the figure below hold equations provided by the add-in. Columns that participate in the solution process are the State Value (Column Q) and the Next Value (column R). The goal of this optimization is to find the action for each state that maximizes the State Value. In this case the state value is the number of runs produced during an inning of play. An iterative process finds the optimum action for each state. They are represented in the table below by the Action Index column and the Action Name column. The iterative dynamic program terminates when the State Value and Next Value are close enough. This is indicated by the Maximum Value Difference that is computed as the maximum absolute value difference between the State Value and Next Value. The iterative process also determines the state probabilities for the optimum policy. These are computed in columns S and T. They aren't very interesting for this example since the process always terminates in the final state.
  The values shown in columns Q through T are the initial values. We will see that these values converge to the optimum values after the application of dynamic programming.


Actions and Events


The actions and event definitions are transported to the DP Solver model as shown on the left. The columns labeled Runs and Probabilities are irrelevant for this example. The number of runs and the probabilities of transition are not a function of either the action or event alone. Run production depends in a complex way on the state, action and event. The probability of a transition depends on the action and event. These are all defined in the transition blocks discussed below.




The first six columns of the decision list are copied from the model. Columns AM through AP compute values necessary for optimization. Only 34 of the decisions are shown. There are 78 decisions for this problem, each characterized by a state and an action.





There are 402 transitions described for this problem. A few are shown on the transition list below. Most of the data is copied directly from the model lists. The final two columns are important for computing the results of the DP.



We solve the DP by clicking on the Solve button at the top of the page. There are several solution options. We choose to solve the DP with the Policy method. This finds the optimum policy in one step. The results are shown below.

The optimum action is found for each state. It happens for this data that the optimum solution is the Hit action, no matter what the state. Although this seems like an uninteresting policy, it is one that couldn't be determined without this kind of analysis.


An interesting result is the State Value for the initial state (0,0,0,0), no outs and no one on base. The value is 0.8122. That is the expected run production in the inning when the optimum policy is followed.


Alternative Data


To illustrate the flexibility of the DP Models add-in with different data, we change the data table to represent a player with less power but more speed. The new data is shown at the left. The new solution is shown below.

The solution describes a policy that involves more base stealing. The expected runs in the inning with this policy is reduced to 0.2916 runs per inning. The faster team has a different strategy but with less scoring.




The model involved a single inning with one kind of player. The rules of baseball were followed, but not all the events were accurately modeled. The biggest assumption is that all batters and runners have equal skills. It would be interesting to describe a batting order for the inning so that each player had a different action/event probability matrix. Assuming a nine place batting order, the model would be at least nine times the size of this model, but it would fit the Excel worksheet. No attempt has been made to model or solve the larger problem.

Return to Top

tree roots

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