didppy.ACPS

class didppy.ACPS(model, f_operator=0, primal_bound=None, time_limit=None, get_all_solutions=False, quiet=False, initial_registry_capacity=1000000, width_init=1, width_step=1, width_bound=None, reset_width=False)

Anytime Column Progressive Search (ACPS) solver.

This performs ACPS 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 cannot compute the cost correctly and 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 the type of primal_bound and the cost type of model are different.

  • 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), 2023.

Sataya Gautam Vadlamudi, Piyush Gaurav, Sandip Aine, and Partha Pratim Chakrabarti. “Anytime Column Search,” Proceedings of AI 2012: Advances in Artificial Intelligence, pp. 254-255, 2012.

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.ACPS(model, quiet=True)
>>> solution = solver.search()
>>> 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.ACPS(model, f_operator=dp.FOperator.Max, quiet=True)
>>> solution = solver.search()
>>> 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.ACPS(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.ACPS(model, quiet=True)
>>> solution, terminated = solver.search_next()
>>> solution.cost
1
>>> terminated
True