DIDPPy provides a number of solvers. This document provides a guideline to select an appropriate solver for your DP model.
In general, we recommend using
CABS if possible.
It has the following advantages:
Anytime: it usually finds a feasible solution quickly and improves the solution quality over time.
Complete: it is guaranteed to find an optimal solution or prove the infeasibility of the model given sufficient time.
Memory efficient: it consumes less memory compared to other solvers.
However, it has the following disadvantages:
It may take a longer time to prove the optimality compared to other solvers.
A configuration is needed to handle certain types of DP models as it searches layer by layer.
Cost expressions must be in the form of addition, product, maximum, or minimum.
Time to Prove Optimality
CABS is sometimes slow to prove the optimality.
This does not mean that
CABS is slow to find an optimal solution; it just takes time to prove the optimality of the found solution.
If you want to prove the optimality as fast as possible,
CAASDy might be a choice.
One disadvantage of
CAASDy is that it is not an anytime solver: it does not find any solution until it proves the optimality.
If you want to use anytime solvers, consider
However, these alternatives consume more memory than
didppy.CABS, so if the memory limit is a concern, they may not be a good choice.
The experimental comparison of
CAASDy and the anytime solvers is provided in Kuroiwa and Beck .
If the time to prove optimality is not very important, and you want to find a good solution quickly,
LNBS may be also useful.
It is slower than
CABS to prove the optimality, but it tends to find a better solution quickly in routing and scheduling problems such as TSPTW and talent scheduling.
CABS is better in MOSP for example.
DP solvers typically search the state space: they generate states that are reachable from the target state using transitions. They store the states encountered in memory and check if it has been encountered before each time a state is generated. In this way, DP solvers save computational time by avoiding evaluating the same state multiple times at the expense of the computational space.
CABS searches layer by layer:
in the \(i\) th iteration, it searches states that are reachable from the target state using \(i\) transitions.
CABS only stores the states in the current layer in memory.
However, in some problems, a state can belong to multiple layers, i.e., the state can be reached from the target state with different numbers of transitions.
It is also possible that a state space contains cycles: a state can be reached from itself with a finite number of transitions.
In such a case, we may want to store states not only in the current layer but also in the previous layers.
We can do that by using
keep_all_layers=True when creating a solver.
solver = dp.CABS(model, keep_all_layers=True)
Restriction on Cost Expressions
w + dp.IntExpr.state_cost()
w * dp.IntExpr.state_cost()
w is an
IntExpr independent of
For float cost, we can use
FloatExpr instead of
CABS assumes that
cost is the additive form.
For other types of
cost, we need to tell the solver by using the argument
f_operator, which takes either of
Plus is the default).
An example is provided in as an advanced tutorial.
This restriction is shared by the following path-finding (or heuristic search) based solvers:
ForwardRecursion supports arbitrary cost expressions.
However, it does not support cyclic state spaces.