Branch and Bound (BnB)

The Simplest Explanation

You're searching for the best solution in a huge space. Instead of checking every possibility, branch (split the problem into subproblems) and bound (compute a lower bound for each). If a subproblem's lower bound is already worse than the best solution you've found, prune it — skip it entirely.

BnB = systematic enumeration + smart pruning. It's exact (always finds the optimal) but uses bounds to avoid exploring branches that can't possibly be optimal.

How BnB Works (Intuition)

Imagine searching for the cheapest flight route. You've found one for $500. Now you're considering a different route, and the cheapest connecting flights alone cost$600. You can stop exploring this route — it can't possibly beat $500.

BnB does this systematically:

1. Find an initial solution (any valid solution) → gives an upper bound (UB)
2. Branch: split the problem into subproblems
3. For each subproblem, compute a lower bound (LB) — the best this branch could possibly achieve
4. If LB ≥ UB → prune this branch (it can't improve on what we already have)
5. If the subproblem is fully solved and its cost < UB → update UB
6. Repeat until all branches explored or pruned

The Three Components

1. Branching

Divide the problem into smaller subproblems. Each subproblem fixes one more decision variable.

For TSP: at each level, choose which city to visit next. Branching creates a tree where each path from root to leaf is a potential tour.

2. Bounding

Compute a lower bound for each subproblem — the minimum possible cost for any solution in this branch.

Common methods for TSP lower bounds:

• Reduced cost matrix: subtract the minimum from each row and column. The total reduction is a lower bound.
• Minimum spanning tree (MST): the MST of unvisited cities is a lower bound on the remaining cost.
• 1-tree bound: an MST plus the two cheapest edges from the partial tour to unvisited cities.

3. Pruning

If $\text{LB} \geq \text{UB}$, prune the branch. No solution in this subtree can beat the current best.

The Algorithm

1. Compute initial UB using a heuristic (e.g., nearest neighbor)
2. Initialize active node set with the root (empty partial solution, LB = 0)
3. While active nodes exist:
   • Pick the node with the lowest LB (most promising)
   • If LB ≥ UB → prune (remove from active set)
   • Branch: generate children by extending the partial solution
   • For each child:
     • Compute LB
     • If LB ≥ UB → prune
     • If complete solution with cost < UB → update UB
     • Else → add to active set
4. Return the best solution found

Lower Bound: Reduced Cost Matrix

The most common bounding method for TSP.

How It Works

1. Start with the distance matrix
2. Row reduction: subtract the minimum from each row. Add all row minima to the lower bound.
3. Column reduction: subtract the minimum from each column. Add all column minima to the lower bound.
4. The total reduction = lower bound on any tour through these cities

Example with 4 Cities

Original distance matrix:

Row minima: A=5, B=2, C=3, D=2 → Row reduction = 12

After row reduction:

Column minima: A=3, B=0, C=1, D=0 → Column reduction = 4

Total lower bound = 12 + 4 = 16

Since we know a tour costing 18 exists (A→B→C→D→A), the gap between LB=16 and UB=18 is only 2. This tight bound is why BnB can be effective.

Worked Example: BnB on 4-City TSP

Using the 4-city TSP from above. Nearest neighbor from A gives A→B→D→C→A = 5+2+4+8 = 19. So UB = 19.

BnB Trace Summary

Optimal tour: A→B→C→D→A = 18

BnB evaluated 7 nodes instead of 6 possible tours (6 permutations for 4 cities). The savings are small here but become enormous for larger instances.

BnB Variants

Best-First Search (Most Common)

Always expand the node with the lowest LB. This finds the optimal solution fastest because the most promising branches are explored first.

Depth-First BnB

Explore one branch to completion first (like DFS). Use the completed solution to update UB, then backtrack. Memory-efficient but may explore more nodes.

Breadth-First BnB

Explore all nodes at one level before going deeper. Uses more memory but gives a clearer picture of the search space.

Properties Summary

BnB for Other Problems

Branch and Bound isn't just for TSP. It applies to any optimization problem where you can:

• Branch: divide into subproblems
• Bound: compute optimistic estimates (lower bounds for minimization)