Branch and bound: complete search with bounds pruning suboptimal branches.
Track best solution (incumbent).
Compute optimistic bound for partial solutions.
Prune if bound incumbent.
TSP example:
- Incumbent: best tour found
- Bound: path cost + MST of remaining cities
- Prune if bound incumbent
Guarantees optimal while exploring fewer nodes than brute force.