A cost paid only if an activity happens at all needs a binary tied to the continuous activity by x ≤ M y. The link works for any M large enough, and that is the trap: every unit above the smallest valid value weakens the relaxation's bound, because the relaxation is then free to open a facility for a fraction of its fixed cost. The price is measurable, in bound and in nodes, on your own instance.
Core ideas
The link itself is one inequality and takes a minute. The lesson is the constant in it, which is a modelling decision with a measurable price and no error message.
x ≤ M y with y binary. At y = 0 the row reads x ≤ 0, which with x ≥ 0 forces x = 0: no activity without the decision. At y = 1 it reads x ≤ M, which is slack provided M is large enough. Note what it does not do: y = 1 never forces x to be positive, so paying a fixed cost for nothing stays feasible and is simply never optimal.
M must permit every x the rest of the model allows, so any upper bound on x is valid and the smallest such bound is best. A facility ships no more than its own capacity and no more than the whole demand, so the smaller of those two is valid and nothing smaller is. “A million” is not a reason; “total demand is 30” is.
The relaxation does not have to choose y ∈ {0, 1}; it sets y = x/M, which is the cheapest value satisfying the row. Its effective unit cost becomes c_j + f_j/M, falling as M grows — so the bound decays toward the fixed costs being free. On the lab's instance the bound goes from 240, which is the answer, to 70; and the search that must close that gap goes from one node to five.
The material
The fixed-charge row, the reason behind a valid M, and the measured cost of a careless one.
A fixed charge is a cost f incurred if an activity x is positive and not otherwise. Modelling it needs a binary y with f y in the objective and the linking constraint x ≤ M y, where M is a constant at least as large as any feasible value of x.
The facility-location problem is this device repeated. Facilities have opening costs f_j, unit shipping costs c_j and capacities; demand must be met; and the objective is Σ f_j y_j + Σ c_j x_j. Without the binaries the model would ship a trickle from every facility and pay no opening cost at all, which is not what a warehouse costs.
Facility 1 costs 200 to open and 2 a unit; facility 2 costs 60 to open and 6 a unit. Each can handle 40 units and demand is 30. Opening facility 1 costs 200 + 60 = 260; opening facility 2 costs 60 + 180 = 240. So the answer is 240, and every figure below is about how well a relaxation knows it.
The tightest valid M here is 30: no facility can ship more than the total demand, whatever its capacity says. At M = 30 the relaxation returns y₂ = 1 whole, a bound of 240, and a search tree that closes in a single node — the bound is the answer, so there is nothing left to prove.
Put M = 600, twenty times the tightest, and nothing about feasibility changes. The relaxation now ships all thirty units from facility 1 and sets y₁ = 30/600 = 1/20, paying a twentieth of the opening cost: 10 + 60 = 70. The bound has fallen from 240 to 70 while the answer stayed 240, and the tree needs five nodes instead of one to prove it.
The shape of that column is the algebra: with y_j = x_j/M the objective contributes c_j x_j + f_j x_j/M, so facility j has an effective unit cost of c_j + f_j/M. As M grows the fixed cost is amortised over a larger and larger notional capacity, and the relaxation drifts toward the model in which opening a facility is free.
That also explains the bend. At small M, facility 2 is cheaper per unit: 6 + 60/30 = 8 against 2 + 200/30 = 26/3. The two cross where 2 + 200/M = 6 + 60/M, which is 140/M = 4, so M = 35 — and there the bound is exactly 1620/7. Above that value the relaxation prefers to half-open the expensive-to-build, cheap-to-run facility, and the bound decays from there without ever coming back.
Two things are worth separating. A loose M does not make the model wrong: every value in the table above returns the same integer answer, 240. What it costs is the bound, and therefore the proof and the work — which on a real instance is the difference between a tree that closes and one that does not.
An M that is too small is a different and worse failure. It is not a weak bound, it is a wrong model: the row x ≤ M y then forbids shipping quantities the situation permits, and the answer it returns is the optimum of a problem nobody asked about. This is why the reason matters more than the number: “the facility's capacity” cannot be too small, and a value chosen by feel can be.
Interactive
A binary linked to an activity, and the bound you pay for every unit of slack in the link
Method
Five steps, and the second is the one that separates a modelling decision from a habit.
f y in the objective and x ≤ M y in the rows. One without the other is either a cost nothing controls or a decision nothing charges for, and both produce models that solve and mean nothing.
“This facility's capacity.” “Total demand.” “The largest order any customer can place.” Then take the smallest of the bounds you can justify. The words are the deliverable; the number is derived from them.
A y at 1/20 is the relaxation telling you what it bought. Anything strictly between 0 and 1 means a fixed cost has been charged fractionally, which is the one thing the binary existed to prevent.
Same instance, two values of M, two bounds and two node counts. “A loose M is bad practice” is folklore; “on this instance it moved the bound from 240 to 70 and the tree from one node to five” is an engineering result.
In the model, as a comment or a line of prose. Six months later the only way to tell a justified M from a guess is that the justified one says why, and the only way to safely tighten one is to know what it was bounding.
One instance, solved exactly at each M. The answer never moves; everything else does.
The first row of that table is the one to want. At the tightest M the relaxation returns a whole y and a bound equal to the answer, so the search closes immediately — the model did the work that would otherwise be a tree.
Notice that the node count jumps from one to five as soon as M leaves its tightest value and then stops changing. The bound keeps decaying smoothly, the work does not: a weaker bound costs nothing until it stops closing a node, and then it costs a subtree. That is why the price of a loose M has to be measured rather than estimated.
For a faded rehearsal, use the lab's demand slider to raise demand to 45 and re-derive the tightest valid M. The supplied first move is that total demand is no longer the binding bound — 45 exceeds either capacity, so the capacity is now what limits a single facility. Say what the tightest M becomes and why, then check the panel, and then say whether one facility can still meet demand alone.
You should be able to write a fixed-charge link and say what each value of the binary forces, justify the tightest valid M from an upper bound on the activity, predict which facility a loose M makes the relaxation half-open, and report the bound and the node count at two values of M on the same instance.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.