Branch and bound, traveling salesman, and knapsack
When variables must be integers, optimization becomes fundamentally harder. Rounding the continuous solution often gives a poor answer. Branch and bound systematically searches the integer solution space using LP relaxations as bounds. Classic problems like the traveling salesman and knapsack showcase both exact and heuristic approaches.
Branch and bound solves integer LPs by exploring a tree of sub-problems. Each node solves an LP relaxation. Branches where the bound is worse than the best known integer solution are pruned.
Key insight: The LP relaxation bound guides the search. Tighter bounds mean more pruning and faster solutions. This is why LP solving speed matters even for integer problems.
Find the shortest tour visiting every city exactly once. The TSP is NP-hard, but heuristics like nearest-neighbor and 2-opt local search find good solutions fast. Compare with the brute-force optimal on a small instance.
6 cities: nearest neighbor heuristic builds a quick tour, 2-opt improves it by swapping edges, and brute force finds the true optimum.
Key insight: 2-opt improves tours by swapping edge pairs. It typically gets within 5-10% of optimal on random instances. The gap between heuristic and optimal shrinks for structured problems.
Select items with given weights and values to maximize total value without exceeding capacity. Dynamic programming solves this exactly, but the greedy heuristic (best value-to-weight ratio first) sometimes fails.
The DP table fills cell by cell: dp[i][w] = max value using items 1..i with capacity w. The highlighted path traces the optimal selection. Greedy (by value/weight ratio) may differ from optimal.
Key insight: The DP table reveals the optimal substructure: the best solution for capacity w using items 1..i builds on solutions for smaller sub-problems. This is the essence of dynamic programming.