didppy.APPS

class didppy.APPS

Anytime Pack Progressive Search (APPS) solver.

This performs APPS using the dual bound as the heuristic function.

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 may not produce the optimal solution.

Parameters:
  • model (Model) – DyPDL model to solve.

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

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

  • get_all_solutions (bool, default: False) – Return a solution if it is not improving when search_next() is called.

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

  • initial_registry_capacity (int, default: 1000000) – Initial size of the data structure storing all generated states.

  • width_init (int, default: 1) – Initial value of the width.

  • width_step (int, default: 1) – Amount of increase of the width.

  • width_bound (int or None, default: None) – Maximum value of the width.

  • reset_width (bool, default: False) – Reset the width to width_init when a solution is found.

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

  • OverflowError – If initial_registry_capacity, width_init, width_step, or width_bound is negative.

  • PanicException – If time_limit is negative.

References

Ryo Kuroiwa and J. Christopher Beck. “Solving Domain-Independent Dynamic Programming with Anytime Heuristic Search,” Proceedings of the 33rd International Conference on Automated Planning and Scheduling (ICAPS), pp. 245-253, 2023.

Sataya Gautam Vadlamudi, Sandip Aine, Partha Pratim Chakrabarti. “Anytime Pack Search,” Natural Computing, vol. 15(3), pp. 395-414, 2016.

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.APPS(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.APPS(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_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.APPS(model, 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.APPS(model, quiet=True)
>>> solution, terminated = solver.search_next()
>>> solution.cost
1
>>> terminated
True