optional · interactive figures

Explore: Lagrangian relaxation

Pick a price and read the bound it gives, watch subgradient steps zig-zag or settle, and see 1-trees become a tour.

optional: nothing in the lab depends on itback to the slides

11 · explore

Pick a price, read the bound

Try: drag the dot to u = 1, 4/3 and 2; watch which items are bought and the sign of g. Static version: L(u) on a three-variable example.

11 · explore

Try: step through λ fixed (it zig-zags forever), then switch to halving. Static version: subgradient steps, on the example.

11 · explore

Try: step the five cities (one step to a tour), then the seven, where the bound drops before it climbs. Static version: a 1-tree on five cities.