3. Generic Branch & Bound Algorithm
- The generic structure of the algorithm
- How nodes are stored and selected
- Where bounds are computed
- How pruning integrates into the flow
- Different search strategies (DFS, BFS, Best-first)
In Part 2, we introduced the core ideas: branching, bounding, and pruning.
Now we organize these ideas into a generic algorithm that can be applied to a wide range of optimization problems.
3.1 High-Level Structure
Branch & Bound explores a search tree while maintaining a set of nodes that are candidates for expansion.
At a high level, the algorithm repeatedly:
- Selects a node
- Evaluates its bound
- Decides whether to prune or expand
- Updates the best solution if needed
3.2 Generic Pseudocode
Initialize node set with root
while node set is not empty:
select a node N
if N is a complete solution:
update best if better
else:
compute bound B(N)
if B(N) is promising:
branch and add children to node set
else:
prune N
This structure captures the essence of Branch & Bound: systematic exploration guided by bounds.
3.3 Node Selection Strategy
The order in which nodes are explored has a major impact on performance.
- DFS (Depth-first): low memory, fast to find a solution
- BFS (Breadth-first): explores level by level
- Best-first: expands the most promising node first
Best-first search is often preferred because it quickly finds strong incumbents, improving pruning effectiveness.
3.4 The Node Set (Frontier)
The algorithm maintains a collection of nodes waiting to be explored. This is often called the frontier.
The data structure depends on the strategy:
- Stack → DFS
- Queue → BFS
- Priority Queue → Best-first
3.5 Updating the Incumbent
Whenever a complete feasible solution is found, it is compared with the current best.
If it improves the objective:
- update the incumbent
- tighten pruning conditions
This makes the algorithm progressively more selective.
3.6 Where Pruning Happens
Pruning occurs immediately after computing the bound.
If the bound cannot beat the incumbent → discard node
This avoids generating unnecessary children and reduces the search space dramatically.
3.7 Key Properties
- Systematic exploration of the search space
- Guided by bounds
- Pruning guarantees efficiency
- Still guarantees optimality
Next: Part 4 — Bounding Functions
Now that we understand the algorithmic structure, the next critical component is how bounds are computed.
In Part 4, we will study bounding functions in detail, including how to design tight and efficient estimates.