# 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.