Branch-and-bound: expand the most promising node first

How to read this

Boxes are nodes of the state-space tree, numbered in the order they are generated (as in Levitin §12.2). Each shows the choice it adds and its bound.

Assignment problem. A node fixes jobs for the first few people. Its lower bound (lb) is the cost already committed plus, for every person still unassigned, the cheapest job still free. No completion can cost less than lb. In the matrix, blue cells are committed, yellow-ringed cells are the row minima that make up the rest of the bound.

Knapsack. Items are sorted by value per unit weight. A node records the weight w and value v of the items taken so far; its upper bound (ub) = v + (W − w) · (value/weight of the next item): fill the leftover room with the best remaining payoff rate, as if items could be cut. The bar shows w (blue) and that imaginary fill (yellow).

Terminated nodes (red) are cut for one of three reasons: the bound is not better than the best solution found so far, the node breaks a constraint (too heavy), or it is a complete solution that is worse than the best one.

Try this

1. Book assignment instance. Predict the root bound before pressing play: 2 + 3 + 1 + 4 = 10. The search generates only 10 nodes (0–9) and finds cost 13 = a→2, b→1, c→3, d→4. Exhaustive search would check all 4! = 24 assignments.
2. Turn on Predict mode and guess each time which live node gets expanded. Why is node 5 (lb = 13) expanded before node 6 (lb = 14) even though both are on the same branch?
3. Book knapsack instance (W = 10). The root's ub is 0 + 10 · 10 = 100. The optimal subset {1, 3} worth $65 appears at node 8, after which nodes 2 (ub 60) and 6 (ub 64) are cut. Now tick “update best from every feasible node”: node 5 already has value 65, so which nodes die earlier?
4. Press Random for a 5 × 5 matrix a few times. How many of the 5! = 120 complete assignments does branch-and-bound actually generate? When does it do badly?
5. Make the bound useless: set every entry of the matrix to the same number. Every lb equals every cost, so nothing can be pruned early. Watch the tree grow.