Computation - Operations Research Models and Methods

Computation

Dynamic Programming


DTMC Tour


CTMC Tour

Download

Dynamic Programming Collection

The Dynamic Programming Collection is a series of add-ins associated with processes that involve states, actions and events. Many situations can be described by a collection of mutually exclusive states. Say we have a situation where the state is observed over time. The system will begin in some initial state. A decision maker has a set of alternative actions. He will choose one of these based on the current state. Some reward may be earned by the current state and the selected action. We call the combination of the state and action a decision.

The decision will cause the system to change from the initial state to a new state. The change in state is called a transition. When the state reached via the transition is assuredly determined, the model is called a deterministic dynamic program.

When the resultant state is uncertain, we say that the state is determined by some event, where the probability of the event is given. Each decision determines a collection of mutually exclusive events with the total probability of the collection equal to 1. When the results of decisions are uncertain the model is called a stochastic dynamic program.

Dynamic programming is considered in three add-ins of the ORMM collection. They can be used together or in some cases separately to construct and solve significant dynamic programming problems.

The picture shows the ORMM menu when the DP add-in collection is installed. Each add-in has an individual role. The DP Data add-in accepts data concerning general situations and calls the DP Models add-in to construct models. The DP Models add-in calls the DP Solver add-in to obtain numerical solutions.

The DP Models add-in also models Markov Chain problems. These are described by states and events alone. No actions are involved. Models constructed can either be analyzed with the DP Solver add-in or the Markov Analysis add-in.

Markov Decision Processes are subsumed under this discussion as they are similar to stochastic dynamic programming models.

This page provides brief introductions to the three add-ins. The first column on the table below has links to download the individual add-ins. The second column provides brief introductions. The titles link to more lengthy descriptions appearing elsewhere on this site. Click the Start/Finish link in the left margin to learn about adding and deleting buttons on pages. If you use any of the example worksheet pages you must learn to use this command. Be sure to read the general instructions for installing add-ins before attempting to use them.

	DP Examples This section holds a number of examples solved with the add-ins of the Dynamic Programming add-ins. The examples illustrate the type of problems that are addressed and the result models used for analysis. Some of the examples are drawn from the literature.

dp_data.xla	DP Data The DP Data add-in provides the data structure for a selected set of problems used to illustrate the remaining add-ins. This add-in has some interesting problem classes of operations research and can be revised to include new classes. The DP Data add-in will call the DP Models add-in and fill the forms created by that add-in.

dp_models.xla	DP Models The DP Models add-in constructs a form that describes the states, actions and events characterizing a given problem. It is an algebraic model generator similar to GAMS used for Mathematical Programming models. The form constructed by the DP Models add-in holds the definitions of the states, actions and events for the problem, formulas for computing the objective function, and formulas for computing the transitions from one state to another. The forms are filled by the DP Data add-in for certain problem classes. The DP Models add-in constructs lists of states, actions, events, decisions and transitions that are used by the DP Solver add-in. The DP Models add-in can also be used directly for problems not modeled by the DP Data add-in.

dp_solver.xla	DP Solver The DP Solver add-in creates a form holding lists of states, actions, events, decisions and transitions. The add-in uses these lists with iterative algorithms to find optimum actions for the states. The add-in handles, deterministic DP models, stochastic DP models, and discrete time markov chains (DTMC) models. Several solution strategies are provided.

markov_analysis.xla	Markov Analysis The DP Models add-in also constructs Markov Chain models. A button on the the model page calls the Markov Analysis add-in. This add-in can also be called from DP Solver worksheets to analyze particular decision selections. This Markov Analysis add-in performs a variety of computations associated with DTMC (Markov Chains) and CTMC (Markov Processes) including: economic analysis, steady state analysis, computation of n-step probabilities, simulation, computation of first passage probabilities and computation of absorbing state probabilities.