BranchAndBound
- class bnbpy.cython.search.BranchAndBound
Bases:
objectClass for solving optimization problems via Branch & Bound.
This class adopts a DFS strategy by default, but can be easily customized by subclassing.
Some alternative strategies are already implemented as subclasses:
BreadthFirstBnB: Breadth-first Branch & Bound algorithm.
DepthFirstBnB: Depth-first Branch & Bound algorithm (alias of BranchAndBound).
BestFirstBnB: Best-first Branch & Bound algorithm.
Useful methods for subclassing and custom implementations:
Callback methods:
pre_eval_callback: Before node bound evaluation.
post_eval_callback: After node bound evaluation.
enqueue_callback: After node is enqueued.
dequeue_callback: After node is dequeued.
solution_callback: When a new feasible solution is obtained (after being set).
Core methods:
enqueue: Include new node into queue.
dequeue: Chooses the next evaluated node and computes its lower bound.
branch: From a given node, create children nodes and enqueue them.
For a customization of enqueueing and dequeueing strategies, it is recommended subclassing BranchAndBound with a customized queue attribute by subclassing BasePriQueue too.
Instantiate algorithm to solve problems via Branch & Bound.
Note that the Cython implementation uses static typing, so the Problem class must be a subclass of bnbpy.cython.problem.Problem.
- Parameters:
rtol (float, optional) – Relative tolerance for termination, by default 1e-4
atol (float, optional) – Absolute tolerance for termination, by default 1e-4
eval_node (Literal['in', 'out', 'both'], optional) –
Node bound evaluation strategy, by default ‘out’.
’in’: call Problem.calc_bound after parent branch, before inserting child nodes in the active queue. Useful when bound computation is inexpensive.
’out’: call Problem.calc_bound after selecting a node from the active queue. The result guides whether to explore (is_feasible, possibly branch) or prune. Often paired with fast enqueue proxies for node quality, such as MILP pseudo-costs.
’both’: evaluate in both moments above.
save_tree (bool, optional) – Whether to save node relationships, by default False. It can consume a lot of memory in large trees.
- branch(node)
From a given node, create children nodes and enqueue them
- Parameters:
node (Node) – Node being evaluated
- dequeue()
Chooses the next evaluated node and computes its lower bound
- Returns:
Node to be evaluated
- Return type:
- dequeue_callback(node)
Abstraction for callbacks after node is dequeued
- enqueue_callback(node)
Abstraction for callbacks after node is enqueued
- post_eval_callback(node)
Abstraction for callbacks after node bound evaluation
- pre_eval_callback(node)
Abstraction for callbacks before node bound evaluation
- solution_callback(node)
Abstraction for callback when a candidate feasible solution is verified (before being set)
- solve(problem, maxiter=None, timelimit=None)
Solves optimization problem using Branch & Bound.
Note that the Cython implementation uses static typing, so the Problem class must be a subclass of bnbpy.cython.problem.Problem.
- Parameters:
problem (Problem) – Problem instance as in root node
maxiter (Optional[int], optional) – Maximum number of iterations, by default None
timelimit (Optional[Union[int, float]], optional) – Time limit in seconds, by default None
- Returns:
Search results containing best solution and problem instance
- Return type: