Dynamic programming (DP) has quite a different
model form than the other types of mathematical programming.
Instead of an objective function and constraints, dynamic
programming models consist of a collection of equations
that describe a sequential decision process.
The process begins in some initial state,
the first decision moves it to a second state, and then
continues through alternating decisions and states until
a final state is reached. For a given problem, the model
must provide:
- mathematical vectors that describe states and decisions
- initial and final state definitions
- transition functions that map the current state and
decision to the next state in the sequence
- the objective function that evaluates the sequence
of decisions
Many problems are naturally described as a sequential
decision process and are ready candidates for a DP solution.
Others that seem more naturally stated as Integer Programming
models can be adapted to the DP format. DP has an advantage
over other formulations in that it does not require linearity.
One difficulty with DP is the curse of dimensionality.
DP solves for the optimal solution from every feasible state.
If the number of feasible states is too large, a very long
time might be required to solve a problem.
This DP add-in provides a general structure
with which most problems appropriate for DP can be modeled
and solved.
