didppy.LNBS

class didppy.LNBS(model, time_limit, f_operator=Ellipsis, primal_bound=None, quiet=False, initial_solution=None, initial_beam_size=1, keep_all_layers=False, max_beam_size=None, seed=2023, has_negative_cost=False, use_cost_weight=False, no_bandit=False, no_transition_mutex=False, cabs_initial_beam_size=None, cabs_max_beam_size=None, threads=1, parallelization_method=Ellipsis)

Large Neighborhood Beam Search (LNBS) solver.

This performs LNBS using the dual bound as the heuristic function. LNBS is complete, i.e., eventually finds the optimal solution, but is designed to find a good solution rather than proving the optimality. If you want to prove the optimality, didppy.CABS or didppy.CAASDy might be better. LNBS typically performs better when the dual bound functions are not tight.

To apply this solver, the cost must be computed in the form of x + state_cost, x * state_cost, didppy.max(x, state_cost), or didppy.min(x, state_cost) where, state_cost is either of IntExpr.state_cost() and FloatExpr.state_cost(), and x is a value independent of state_cost. Otherwise, it cannot compute the cost correctly and may not produce the optimal solution. if x can be negative, please set has_negative_cost to True.

LNBS searches layer by layer, where the i th layer contains states that can be reached with i transitions. By default, this solver only keeps states in the current layer to check for duplicates. If keep_all_layers is True, LNBS keeps states in all layers to check for duplicates.

Note that a solution found by this solver may not apply a forced transition when it is applicable.

Parameters:

  • model (Model) – DyPDL model to solve.

  • time_limit (int or float) – Time limit. This is required for LNBS.

  • f_operator (FOperator, default: FOperator.Plus) – Operator to combine a g-value and the dual bound to compute the f-value. If the cost is computed by +, this should be Plus. If the cost is computed by *, this should be Product. If the cost is computed by max, this should be Max. If the cost is computed by min, this should be Min.

  • primal_bound (int, float, or None, default: None) – Primal bound.

  • quiet (bool, default: False) – Suppress the log output or not.

  • initial_solution (list of Transition or None, default: None) – Initial feasible solution. If None, CABS is is performed to find an initial feasible solution.

  • initial_beam_size (int, default: 1) – Initial beam size.

  • keep_all_layers (bool, default: False) – Keep all layers of the search graph for duplicate detection in memory.

  • max_beam_size (int or None, default: None) – Maximum beam size. If None, the beam size is kept increased until a partial state space is exhausted.

  • seed (int, default: 2023) – Random seed.

  • has_negative_cost (bool, default: False) – Whether the cost of a transition can be negative.

  • use_cost_weight (bool, default: False) – Use weighted sampling biased by costs to select a start of a partial path.

  • no_bandit (bool, default: False) – Do not use bandit-based sampling to select the depth of a partial path.

  • no_transition_mutex (bool, default: False) – Do not remove transitions conflicting with a suffix from a partial state space.

  • cabs_initial_beam_size (int or None, default: None) – Initial beam size for CABS to find an initial feasible solution.

  • cabs_max_beam_size (int or None, default: None) – Maximum beam size for CABS to find an initial feasible solution. If None, the beam size is kept increased until a feasible solution is found.

  • threads (int, default 1) – Number of threads.

  • parallelization_method (BeamParallelizationMethod, default: BeamParallelizationMethod.Hdbs2) – How to parallelize the search. When threads is 1, this parameter is ignored.

Raises:

  • TypeError – If primal_bound is float and model is int cost.

  • PanicException – If time_limit is negative or CABS raises an exception when finding an initial solution.

References

Ryo Kuroiwa and J. Christopher Beck. “Large Neighborhood Beam Search for Domain-Independent Dynamic Programming,” Proceedings of the 29th International Conference on Principles and Practice of Constraint Programming (CP), pp. 23:1-23:22, 2023.

Ryo Kuroiwa and J. Christopher Beck. “Parallel Beam Search Algorithms for Domain-Independent Dynamic Programming,” Proceedings of the 38th Annual AAAI Conference on Artificial Intelligence (AAAI), 2024.

Examples

Example with + operator.

>>> import didppy as dp
>>> model = dp.Model()
>>> x = model.add_int_var(target=1)
>>> model.add_base_case([x == 0])
>>> t = dp.Transition(
...     name="decrement",
...     cost=1 + dp.IntExpr.state_cost(),
...     effects=[(x, x - 1)]
... )
>>> model.add_transition(t)
>>> model.add_dual_bound(x)
>>> solver = dp.LNBS(model, time_limit=1800, quiet=True)
>>> solution = solver.search()
>>> print(solution.cost)
1

Example with max operator.

>>> import didppy as dp
>>> model = dp.Model()
>>> x = model.add_int_var(target=2)
>>> model.add_base_case([x == 0])
>>> t = dp.Transition(
...     name="decrement",
...     cost=dp.max(x, dp.IntExpr.state_cost()),
...     effects=[(x, x - 1)]
... )
>>> model.add_transition(t)
>>> model.add_dual_bound(x)
>>> solver = dp.LNBS(model, time_limit=1800, f_operator=dp.FOperator.Max, quiet=True)
>>> solution = solver.search()
>>> print(solution.cost)
2

Methods

search()

Search for the optimal solution of a DyPDL model.

search_next()

Search for the next solution of a DyPDL model.
search()

Search for the optimal solution of a DyPDL model.

Returns:

Solution.

Return type:

Solution

Raises:

PanicException – If the model is invalid.

Examples

>>> import didppy as dp
>>> model = dp.Model()
>>> x = model.add_int_var(target=1)
>>> model.add_base_case([x == 0])
>>> t = dp.Transition(
...     name="decrement",
...     cost=1 + dp.IntExpr.state_cost(),
...     effects=[(x, x - 1)]
... )
>>> model.add_transition(t)
>>> model.add_dual_bound(x)
>>> solver = dp.LNBS(model, time_limit=1800, quiet=True)
>>> solution = solver.search()
>>> solution.cost
1
search_next()

Search for the next solution of a DyPDL model.

Returns:

  • solution (Solution) – Solution.

  • terminated (bool) – Whether the search is terminated.

Raises:

PanicException – If the model is invalid.

Examples

>>> import didppy as dp
>>> model = dp.Model()
>>> x = model.add_int_var(target=1)
>>> model.add_base_case([x == 0])
>>> t = dp.Transition(
...     name="decrement",
...     cost=1 + dp.IntExpr.state_cost(),
...     effects=[(x, x - 1)]
... )
>>> model.add_transition(t)
>>> model.add_dual_bound(x)
>>> solver = dp.LNBS(model, time_limit=1800, quiet=True)
>>> solution, terminated = solver.search_next()
>>> solution.cost
1
>>> terminated
True