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.
