Skip to content

Latest commit

 

History

History
89 lines (67 loc) · 5.34 KB

solver-selection.rst

File metadata and controls

89 lines (67 loc) · 5.34 KB
Raw

Solver Selection

DIDPPy provides a number of :ref:`solvers <api-reference:Solvers>`. This document provides a guideline to select an appropriate solver for your DP model.

In general, we recommend using :class:`~didppy.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

:class:`~didppy.CABS` is sometimes slow to prove the optimality. This does not mean that :class:`~didppy.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, :class:`~didppy.CAASDy` might be a choice. One disadvantage of :class:`~didppy.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 :class:`~didppy.ACPS` and :class:`~didppy.APPS`. However, these alternatives consume more memory than :class:`didppy.CABS`, so if the memory limit is a concern, they may not be a good choice. The experimental comparison of :class:`~didppy.CAASDy` and the anytime solvers is provided in :cite:t:`DIDPAnytime`.

If the time to prove optimality is not very important, and you want to find a good solution quickly, :class:`~didppy.LNBS` may be also useful. It is slower than :class:`~didppy.CABS` to prove the optimality, but it tends to find a better solution quickly in routing and scheduling problems such as :ref:`TSPTW <tutorial:TSPTW>` and :ref:`talent scheduling <advanced-tutorials/forced-transitions:Talent Scheduling>`. In contrast, :class:`~didppy.CABS` is better in :ref:`MOSP <advanced-tutorials/general-cost:MOSP>` for example.

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.

:class:`~didppy.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, :class:`~didppy.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 :class:`~didppy.BreadthFirstSearch` and :class:`~didppy.ExpressionBeamSearch`.

Restriction on Cost Expressions

To use :class:`~didppy.CABS`, the cost expressions (cost in :class:`~didppy.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 :class:`~didppy.IntExpr` independent of :meth:`~didppy.IntExpr.state_cost`. For float cost, we can use :class:`~didppy.FloatExpr` instead of :class:`~didppy.IntExpr`. By default, :class:`~didppy.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 :attr:`didppy.FOperator.Plus`, :attr:`didppy.FOperator.Product`, :attr:`didppy.FOperator.Max`, or :attr:`didppy.FOperator.Min` (:attr:`~didppy.FOperator.Plus` is the default). An example is provided in as an :doc:`advanced tutorial <advanced-tutorials/general-cost>`.

This restriction is shared by the following path-finding (or heuristic search) based solvers:

Currently, only :class:`~didppy.ForwardRecursion` supports arbitrary cost expressions. However, it does not support cyclic state spaces.