didppy.ExpressionBeamSearch

class didppy.ExpressionBeamSearch

Beam search solver using expressions to compute heuristic values.

This performs beam search using user-defined cost expressions as cost and heuristic functions.

To apply this solver, the user-defined 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.

This solver does not have a guarantee for optimality.

Parameters:

  • model (Model) – DyPDL model to solve.

  • beam_size (int) – Beam size.

  • custom_cost_dict (dict[str, Union[IntExpr|IntVar|IntResourceVar|FloatExpr|FloatVar|FloatResourceVar|int|float] or None, default: None) – Expressions to compute g-values. A g-value is the cost of the path from the target state to the current state. A key is the name of a transition, and the value is an expression to compute a g-value. An expression can use IntExpr.state_cost() or FloatExpr.state_cost(), which returns the current g-value. If the name of a transition is not included, its cost expression is used. If None, the cost expressions in the DyPDL model are used for all transitions.

  • h_expression (IntExpr, IntVar, IntResourceVar, FloatExpr, FloatVar, FloatResourceVar, int, float, or None, default: None) – Expression to compute an h-value.

  • f_operator (FOperator, default: FOperator.Plus) – Operator to combine a g-value and the base cost. 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. This solver keeps top b best nodes with regard to f-values at each depth.

  • custom_f_operator (FOperator, default: FOperator.Plus) – Operator to combine a g-value and the h-value to compute the f-value. If the custom cost is computed by +, this should be Plus. If the custom cost is computed by *, this should be Product. If the custom cost is computed by max, this should be Max. If the custom cost is computed by min, this should be Min. This solver keeps top b best nodes with regard to f-values at each depth.

  • maximize (bool, default: False) – Maximize f-values or not. Greater f-values are better if True, and smaller are better if False.

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

  • time_limit (int, float, or None, default: None) – Time limit.

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

  • float_custom_cost (bool or None, default: None) – Use continuous values for g-, h-, and f-values. The cost type of the model is used if None.

Raises:

  • TypeError – If the custom cost type is int and h_evaluator or a value in custom_cost_dict is FloatExpr, FloatVar, FloatResourceVar, or float.

  • OverflowError – If beam_size is negative.

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.ExpressionBeamSearch(model, 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.ExpressionBeamSearch(model, 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()

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.ExpressionBeamSearch(model, quiet=True)
>>> solution = solver.search()
>>> print(solution.cost)
1