didppy.BreadthFirstSearch
- class didppy.BreadthFirstSearch(model, f_operator=Ellipsis, primal_bound=None, time_limit=None, get_all_solutions=False, quiet=False, initial_registry_capacity=1000000, keep_all_layers=False)
Breadth-first search solver.
This performs breadth-first search 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)
, ordidppy.min(x, state_cost)
where,state_cost
is either ofIntExpr.state_cost()
andFloatExpr.state_cost()
, andx
is a value independent ofstate_cost
. Otherwise, it may not produce the optimal solution.Breadth-first 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
isTrue
, this solver keeps states in all layers to check for duplicates.- Parameters:
model (Model) – DyPDL model to solve.
f_operator (FOperator, default: FOperator.Plus) – If the cost is computed by
+
, this should bePlus
. If the cost is computed by*
, this should beProduct
. If the cost is computed bymax
, this should beMax
. If the cost is computed bymin
, this should beMin
.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.
keep_all_layers (bool, default: False) – Keep all layers of the search graph for duplicate detection in memory.
- Raises:
TypeError – If
primal_bound
isfloat
andmodel
is int cost.PanicException – If
time_limit
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.BreadthFirstSearch(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.BreadthFirstSearch(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 for the next solution of a DyPDL model.
- search()
Search for the optimal solution of a DyPDL model.
- Returns:
Solution.
- Return type:
- 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.BreadthFirstSearch(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.BreadthFirstSearch(model, quiet=True) >>> solution, terminated = solver.search_next() >>> solution.cost 1 >>> terminated True