optional · interactive figures

Explore: formulations

How the size of M decides the LP bound, on one facility and on the deck's facility-location instance.

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

05 · explore

Big-M, from one facility to the bound

Try: slide M from 3 to 30 and watch the extra room on the left and the aggregated bound on the right. Static versions: big-M, the two LPs.

What it shows. Left: one facility's load $x$ (the customers it serves, at most 3) against its opening $y$. The integer points are $(0, 0)$ and the thick segment at $y = 1$; the light region is the relaxation with the tightest valid $M = 3$, and the red region is what a larger $M$ adds. The red point is the LP's favourite trick: full load with the facility open only $3/M$. This part is computed in the page.

Right: the deck's two-facility, three-customer instance. The aggregated LP bound for each $M$, the disaggregated bound and the integer optimum 13 were solved by HiGHS (colib.mip.lp_relaxation on the reference ufl_aggregated and ufl_disaggregated, optimum by ufl_brute_force), recorded by slides/viz/traces/u05.py. The bound follows $3 + 18/M$: 9 at $M = 3$, 3.6 at $M = 30$.