What Branch & Bound Solves
Branch & Bound is a general technique for solving combinatorial optimization problems by exploring a search space and pruning branches that cannot lead to an optimal solution.
Conceptually, it extends combinatorial search by associating each partial solution with a bound that estimates the best possible outcome reachable from that state.
Instead of exploring all possibilities, the algorithm focuses on promising regions and discards those that cannot improve the current best solution.
Reference:
the presentation follows the classical treatment used in
algorithm design and combinatorial optimization,
connecting search trees, bounds, and pruning strategies.
Parts
- Part 1 — Problem Model & Search Space
- Part 2 — The Core Idea (Branch + Bound + Pruning)
- Part 3 — Generic Branch & Bound Algorithm
- Part 4 — Bounding Functions
- Part 5 — Node Selection Strategies
- Part 6 — Classic Problems
- Part 7 — Complexity
- Part 8 — Branch & Bound vs Backtracking vs Dynamic Programming