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:

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.

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.