Fundamental Algorithms8 sections · 291 units
Open in Course

Branch and Bound

Complete search with optimal pruning.

Branch and bound: complete search with bounds pruning suboptimal branches.

1.1. Track best solution (incumbent).

2.2. Compute optimistic bound for partial solutions.

3.3. Prune if bound ≥\geq incumbent.

TSP example:

  • Incumbent: best tour found
  • Bound: path cost + MST of remaining cities
  • Prune if bound ≥\geq incumbent

Guarantees optimal while exploring fewer nodes than brute force.