Branch and bound, traveling salesman, and knapsack
Some choices are all or nothing: a city is on the route or it isn't, an item goes in the bag or it doesn't. These demos search such choices for the best one.
Press Next Step to grow the search tree one sub-problem at a time. Watch the LP bound at each node decide which branches get pruned.
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.
Press Compare Tours to race nearest-neighbor and 2-opt against the brute-force optimal tour. Shuffle Cities and see how close the heuristics get.
6 cities: nearest neighbor heuristic builds a quick tour, 2-opt improves it by swapping edges, and brute force finds the true optimum.
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.
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.
Set the capacity and press Fill Table to watch dynamic programming build up the best value cell by cell. Then compare its pick with the greedy choice.
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.
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.
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.
Spot a mistake or have an idea?