Solver Selection

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.
Multi-threading: it can be run in parallel using multiple threads.

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 using a single thread, 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 ACPS and APPS. 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 [2].

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 when the dual bound functions are not tight. For example, LNBS is better than CABS with the DIDP models for TSPTW and talent scheduling. In contrast, CABS is better with the DIDP model for MOSP for example. Note that a solution found by LNBS may not apply a forced transition when it is applicable.

Layer-by-Layer Search

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. By default, 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)

This is also the case for BreadthFirstSearch and ExpressionBeamSearch.

Restriction on Cost Expressions

To use CABS, the cost expressions (cost in Transition) of all transitions must be in either of the following forms:

w + dp.IntExpr.state_cost()
w * dp.IntExpr.state_cost()
dp.max(w, dp.IntExpr.state_cost())
dp.min(w, dp.IntExpr.state_cost())

where w is an IntExpr independent of state_cost(). For float cost, we can use FloatExpr instead of IntExpr. By default, 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 didppy.FOperator.Plus, didppy.FOperator.Product, didppy.FOperator.Max, or didppy.FOperator.Min (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:

Currently, only ForwardRecursion supports arbitrary cost expressions. However, it does not support cyclic state spaces.