Branch & Bound and Pruning — Algorithms Course

What you'll learn

Backtracking finds a solution; branch & bound finds the best one — without exploring the whole tree. The trick is a bound: an optimistic estimate of the best a branch could yield, so you can prune any branch that can't beat what you already have.

By the end you'll be able to:

Turn a search into an optimization with a bounding function
Prune branches that can't improve the best solution
Apply branch & bound to knapsack and TSP

Search for the best

Optimization problems ask for the maximum or minimum, not just any valid answer. You could enumerate every candidate with backtracking and keep the best — but that's the full exponential tree. Branch & bound keeps a running best and uses it to skip subtrees that provably can't win.

Bounding functions

A bound is an optimistic estimate — an upper bound for a maximization problem — of the best value reachable by completing the current partial solution. If even that optimistic estimate can't beat the current best, the entire branch is hopeless and gets cut:

Prune when the bound can't beat the best

best so far = 22

The best complete solution found up to now.

branch A · bound = 27

27 > 22 → could beat best. Explore.

branch B · bound = 19

19 ≤ 22 → hopeless. Prune.

Key idea

The bound must be optimistic but valid: never underestimate a maximization branch, or you might prune the real optimum. A tighter (closer) bound prunes more — the art is a bound that's both safe and sharp.

The template

Branch & bound is backtracking plus one extra line — the bound check:

Language

branch_and_bound.py

best = float("-inf")

def branch_and_bound(state):
    global best
    if is_complete(state):
        best = max(best, value(state))
        return
    if bound(state) <= best:        # optimistic estimate can't beat best
        return                      # prune the entire branch
    for choice in choices(state):
        branch_and_bound(extend(state, choice))

Knapsack & TSP

0/1 knapsack: at each item, branch on take/skip. A good bound fills the remaining capacity fractionally (the fractional-knapsack answer, from Module 14) — always an over-estimate of the 0/1 value, so it's safe to prune against.
Travelling salesman: branch on the next city. Bound a partial tour by adding, for each unvisited city, its cheapest incident edge — a lower bound on any completion. Prune partial tours whose bound exceeds the best complete tour found.

Note

Constraint propagation is pruning's cousin: after each choice, deduce and eliminate values that are now impossible (as in Sudoku, where placing a 5 removes it from its row, column, and box). Less to branch on means a smaller tree.

Recap & quick check

Key takeaways

Branch & bound finds the optimal solution by pruning with a bound.
A bound is an optimistic estimate of the best a branch could reach.
Prune a branch when its bound can't beat the current best solution.
The bound must be valid (never wrong-direction) — tighter bounds prune more.
Knapsack bounds with fractional fill; TSP bounds with cheapest incident edges.

Quick check

1. What does a bounding function estimate?

2. When is a branch pruned in branch & bound (maximization)?

3. What property must a bound have to be safe?

4. A good bound for 0/1 knapsack uses:

One more search setting: when an opponent is choosing against you. Next up: Module 23 — Adversarial Search: Minimax & Alpha-Beta.