optional · interactive figures

Explore: Benders decomposition

Benders' master replayed: what it believes each first-stage choice costs, how each cut corrects it, and the two bounds meeting.

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

12 · explore

What the master believes

Try: step the deck's example (three iterations), then the no-penalty version and the three-facility instance. Static versions: the example, the loop.

What it shows. One bar pair per first-stage choice (which facilities to open). The outline is its true cost: opening cost plus the probability-weighted recourse, solved exactly. The filled bar is what the Benders master believes it costs, from the cuts it has so far. The master picks the lowest filled bar, which is the lower bound; solving the scenarios there gives an upper bound and new cuts, which raise the filled bars. The loop ends when the lowest filled bar reaches the best outline.

The deck's example: none (LB 0, UB 60), then both (LB 16, UB 25), then LB = UB = 25.
All demand must be met: at "none" both scenarios are infeasible, so two feasibility cuts remove every choice with too little capacity.
Three facilities, loose capacities (StochasticFacility.random(3, 4, 2, seed=0, capacity_ratio=3.0)): six iterations, visiting five different choices before the bounds meet. The "none" bar is off the scale and marked with its value.

Data. Recorded by slides/viz/traces/u12.py, which runs the reference multi-cut loop with unit 12's solve_master, second_stage, optimality_cut and feasibility_cut, and evaluates the master's cuts at every choice.