BranchAndBound

class bnbpy.cython.search.BranchAndBound

Bases: object

Class 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:

  • DepthFirstBnB: Depth-first (default) alias of BranchAndBound.

  • BreadthFirstBnB: Breadth-first Branch & Bound algorithm.

  • BestFirstBnB: Best-first Branch & Bound algorithm.

  • LifoBnB: LIFO (last-in, first-out) strategy via LifoManager.

  • FifoBnB: FIFO (first-in, first-out) strategy via FifoManager.

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

  • 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, pass a custom manager (subclass of BaseNodeManager) at construction time, or override enqueue / dequeue in a subclass.

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:

  • problem (Problem) – Problem instance to solve

  • 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 manager. Useful when bound computation is inexpensive.

    • ’out’: call Problem.calc_bound after selecting a node from the active manager. 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.

  • manager (BaseNodeManager, optional) – Node manager that controls the search traversal strategy. Defaults to DepthFirstSearch() (depth-first search) when None is given. Pass any BaseNodeManager subclass to customise the traversal order, or use the build_manager() factory for common string aliases.

branch(node)

From a given node, create children nodes and enqueue them

Parameters:

node (Node) – Node being evaluated

static build_manager(strategy, **options)

Factory method that returns a BaseNodeManager for the given traversal strategy name.

Parameters:

  • strategy (str) –

    One of 'dfs', 'bfs', 'best', 'lifo', 'fifo', 'cbfs'.

    • 'dfs' — Depth-first search (DepthFirstSearch).

    • 'bfs' — Breadth-first search (FifoManager).

    • 'best' — Best-first search (BestFirstSearch).

    • 'lifo' — Last-in first-out stack (LifoManager).

    • 'fifo' — First-in first-out queue (FifoManager).

    • 'cbfs' — Cyclic best-first search (CyclicBestSearch).

  • options (Any) – Additional keyword arguments to pass to the manager constructor.

Returns:

The corresponding manager instance.

Return type:

BaseNodeManager

Raises:

ValueError – If strategy is not one of the recognised names.

dequeue_callback(node)

Abstraction for callbacks immediately after node is dequeued and possibly evaluated.

Parameters:

node (Node) – Node that was dequeued and evaluated (if eval_out is True).

enqueue_callback(node)

Abstraction for callbacks immediately before node is enqueued, already after being evaluated.

Parameters:

node (Node) – Node that is about to be enqueued.

log_row(message)

Log a row to the search logger.

Parameters:

message (Any) – Message to log

post_eval_callback(node)

Abstraction for callbacks after node bound evaluation

pre_eval_callback(node)

Abstraction for callbacks before node bound evaluation

reset()

Reset the search state for a fresh solve.

Clears the queue, incumbent, bound node, and root so that the next call to solve() starts from scratch.

set_solution(node)

Assigns the current node as incumbent, updates gap and calls solution_callback

Parameters:

node (Node) – New solution node

solution_callback(node)

Abstraction for callback when a candidate feasible solution is verified (before being set)

solve(maxiter=None, timelimit=None, rtol=None, atol=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.

Call reset() before solve() to restart from scratch; otherwise a second call to solve() resumes from the current queue state.

Parameters:

  • maxiter (Optional[int], optional) – Maximum number of additional iterations, by default None

  • timelimit (Optional[Union[int, float]], optional) – Time limit in seconds, by default None

  • rtol (Optional[float], optional) – Relative tolerance for termination. If provided, permanently updates self.rtol, by default None

  • atol (Optional[float], optional) – Absolute tolerance for termination. If provided, permanently updates self.atol, by default None

Returns:

Search results containing best solution and problem instance

Return type:

SearchResults

DepthFirstBnB

class bnbpy.cython.search.DepthFirstBnB

Bases: BranchAndBound

Depth-first Branch & Bound algorithm.

Uses DepthFirstSearch as the node manager.

BreadthFirstBnB

class bnbpy.cython.search.BreadthFirstBnB

Bases: BranchAndBound

Breadth-first Branch & Bound algorithm.

Uses a FifoManager as the node manager.

BestFirstBnB

class bnbpy.cython.search.BestFirstBnB

Bases: BranchAndBound

Best-first Branch & Bound algorithm.

Uses a BestFirstSearch as the node manager.

LifoBnB

class bnbpy.cython.search.LifoBnB

Bases: BranchAndBound

Branch & Bound with a last-in first-out (LIFO) node manager.

Uses LifoManager as the node manager. Equivalent to a pure stack-based DFS without bound-based tie-breaking.

FifoBnB

class bnbpy.cython.search.FifoBnB

Bases: BranchAndBound

Branch & Bound with a first-in first-out (FIFO) node manager.

Uses FifoManager as the node manager. Equivalent to a pure queue-based BFS without bound-based tie-breaking.

SearchResults

class bnbpy.cython.search.SearchResults

Bases: object

Results container for Branch & Bound search

Initialize SearchResults

Parameters:

  • solution (Solution) – The best solution found

  • problem (Problem) – The problem instance corresponding to the solution

cost

Cost of the best solution found

lb

Lower bound of the search

solution
status

Optimization status