Cold open
George Stigler set out to find the cheapest diet that could keep a person alive and well: seventy-seven foods at their 1939 prices, no computer. By hand and by judgment alone he arrived at $39.93 a year, published the figure in 1945, and freely admitted he could not prove it the true minimum. A method that could prove it existed nowhere yet; measured from those 1939 prices, it was still nearly a decade off. It arrived in 1947, when George Dantzig's simplex method had nine clerks at the National Bureau of Standards run it for some 120 person-days, settling the question at $39.69, twenty-four cents under his guess[1].
Ten thousand years later, that same mathematics has become plumbing. The General Systems Vehicle Marginal Utility provisions itself every few milliseconds: what to fabricate, what to spend, what to keep in reserve, against limits that shift by the second. It settles Stigler's question, and harder ones, before the thought finishes. Here is how it does that.
Section 01 · The hero figure
A region with corners
What to notice: a best point always sits on the boundary, and a corner always ties for best.
Resting state. Best corner (4, 0), objective 12. The feedstock limit and the floor x2 = 0 form this corner; press time has slack 2.
Deep in the Marginal Utility, a fabricator bay splits its shift between field-tile and shear-foam. Feedstock is scarce, press time is scheduled, and neither limit may be crossed. The Mind wants the most valuable mix it can pour.
Underneath, two variables: maximize 3 x1 + 2 x2 subject to x1 + x2 ≤ 4 and x1 + 3 x2 ≤ 6, both nonnegative. Nonnegativity is a constraint in its own right: at the resting corner (4, 0), the optimum a solver labels x*, the feedstock budget is spent to its last unit and the floor x2 = 0 supplies the other wall. Press time is not even full; it has room to spare, a slack of 2, and a budget with slack buys the objective nothing extra at the margin. Section 04 turns that idea, what one more unit of a limit is worth, into an exact price. Drag a line and the region re-shapes.
With a straight objective on a region this shape, some corner is guaranteed to tie for best. An intersection of half-planes is convex, no dents and no bulges, so a straight line between two feasible points never leaves the region. Sweep the dashed level line up in the arrow's direction and its last feasible contact cannot lie in the interior, since any point with the region on all sides still has room to move higher. So the last contact is a corner or a whole edge, and even when it is an edge, the corners at its ends score the same value; either way a corner ties for best.
Section 02 · The formulation pipeline
From words to a tableau
Click a limit to carve it into the region; each one adds a row and a slack that names the room left over.
Feedstock budget. field-tile and shear-foam each draw one unit of feedstock; four units are on hand. x1 + x2 ≤ 4
Press time. field-tile needs one press pass, shear-foam needs three; six passes fit the shift. x1 + 3 x2 ≤ 6
Both limits active. Best corner (4, 0), objective 12.
ANY PROGRAM FITS THE MOLD
- Minimize a cost? Negate it and maximize: minimize 3 x1 + 2 x2 becomes maximize -3 x1 - 2 x2, same choices, mirrored score.
- A floor, not a ceiling? An at-least row flips sign: x1 + x2 ≥ 2 becomes -x1 - x2 ≤ -2.
- An exact order? An equality is two inequalities worn at once: x1 + x2 = 3 holds when the total is at most 3 and at least 3. Section 6 builds whole network programs from equality rows.
- A quantity free to swing negative? A free variable splits into a difference of two nonnegative parts: write x as u - v with u and v nonnegative.
| basis | x1 | x2 | s1 | s2 | rhs |
|---|---|---|---|---|---|
| s1 | 1 | 1 | 1 | 0 | 4 |
| s2 | 1 | 3 | 0 | 1 | 6 |
| z | 3 | 2 | 0 | 0 | 0 |
The Mind stops pouring long enough to keep books. Beside every budget it writes a second figure, the amount still unspent, so no scrap of capacity goes uncounted. A limit written as an exact balance is easier to solve than a limit written as a warning.
The fab-bay mix stays maximize 3 x1 + 2 x2, but each at-most limit becomes an exact equation once a slack is added: x1 + x2 + s1 = 4 and x1 + 3 x2 + s2 = 6, where s1 and s2 hold the feedstock and press time still to spare. Those equalities are the first rows of the tableau[2]. Two products against two limits is all a plane can draw; the bay's real orders run longer, and the next section scales the same program up until the picture gives out.
Section 03 · The signature
Walking the corners
One scrubber moves both views. The corner that lights up on the left is the same pivot highlighted on the right.
- s1 antimatter budget -x1 + x2 ≤ 5
- s2 chargrid hours x1 + 4 x2 ≤ 45
- s3 hull-frame stock 2 x1 + x2 ≤ 27
- s4 stabilizer mass 3 x1 - 4 x2 ≤ 24
- s5 crystal chamber cap x3 ≤ 4
| basis | x1 | x2 | x3 | s1 | s2 | s3 | s4 | s5 | rhs |
|---|---|---|---|---|---|---|---|---|---|
| s1 | 0 | 0 | 0 | 1 | -3/7 | 5/7 | 0 | 0 | 5 |
| s4 | 0 | 0 | 0 | 0 | 11/7 | -16/7 | 1 | 0 | 33 |
| x2 | 0 | 1 | 0 | 0 | 2/7 | -1/7 | 0 | 0 | 9 |
| x1 | 1 | 0 | 0 | 0 | -1/7 | 4/7 | 0 | 0 | 9 |
| x3 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 4 |
| z | 0 | 0 | 0 | 0 | -1/7 | -3/7 | 0 | -1 | -22 |
Objective after each pivot
Read in exact fractions, the z row's slack prices are the same shadow prices S4 charges for one more unit, computed here as the walk runs.
Resting state, the finished walk. Basis holds s1, s4, x2, x1, x3. Vertex (9, 9, 4). Objective 22. No column improves it, so this corner is optimal.
Back in the same bay, Corner Case, the survey drone, will not cut across the cargo hold. It hops corner to corner along the hull, and at each landing the tableau on the wall redraws itself to match the pose the drone just struck.
Scaled up for a full cargo run, the fab-bay problem outgrows the plane that held it: a third product, phase-crystal, comes online as x3, and the ship restates the job for the bigger bay, maximize x1 + x2 + x3 with each product counted evenly, under five limits of its own[3]. Its best corner sits at (9, 9, 4) with objective 22. Every pivot on that walk is Gaussian elimination on the tableau: the entering column and the leaving row that light up together are one step of row reduction[2]. The walk also knows when to stop: a region with no dents under a flat objective has no false summits, so a corner with no better neighbor is best anywhere, not merely best nearby.
A second knob sits under the walk. Drag the binding hull-frame stock limit off its recorded 27 and both panels leave the trace: the polytope re-enumerates and the walk re-solves live in your browser, a fresh optimum each time. Reset to 27 and every number returns to the recorded walk at (9, 9, 4), objective 22, exactly as our reference solver wrote it; where the live engine cannot load, the knob simply stays put.
Trust the picture only this far. In two or three dimensions you can see the corners; past three there is nothing left to see, the number of corners can climb faster than any screen could hold, and several bases can name the same corner, so the drone seems to pivot without moving. None of that reaches the tableau. The row reduction on the right is the same operation in three dimensions or three hundred, which is why the algebra, not the geometry, is what a solver actually runs.
Three anomalies
When a program has no best corner
The walk you just watched always found a corner to stop at. Not every program is so lucky. Here are three that are not, each drawn straight from its own geometry on the same two-variable chassis as the hero: one with no feasible point at all, one that climbs forever, and one carrying a limit that does no work.
Figure 5. Three programs the fab-bay solver cannot answer with a single corner. Each panel is drawn from its own geometry, not replayed from a recorded walk, so every badge reads drawn from geometry. The infeasible and unbounded panels quote the status our reference solver recorded for them; the redundant case is read straight from the lines. The constraint hues, the violet objective arrow, and the warm corner dot are the hero's, kept throughout.
Section 04 · Duality
What one more unit is worth
What is one more unit worth? Hover or focus a resource to read its shadow price.
The resource limits (primal)
- antimatter budget -x1 + x2 ≤ 5 slack, worth 0
- chargrid hours x1 + 4 x2 ≤ 45 binding, worth 1/7
- hull-frame stock 2 x1 + x2 ≤ 27 binding, worth 3/7
- stabilizer mass 3 x1 - 4 x2 ≤ 24 slack, worth 0
- crystal chamber cap x3 ≤ 4 binding, worth 1
What one more unit is worth (dual)
The price is a slope
At b = 27 the best profit is 22. One more unit of hull-frame stock is worth 3/7 here, the slope of the curve, and holds while the limit stays between 20 and 41.4. With scripts on, drag the limit to watch the slope, and the price, change.
Any feasible set of prices that covers every product is an upper bound on the profit the ship can earn. So once a pricing meets the primal walk at the same figure, neither side can move any further and that figure is certified optimal. Both sides meet here, and the priced stack below reaches exactly that height.
The binding limits, priced and stacked to the profit
antimatter budget is slack, so it adds 0 stabilizer mass is slack, so it adds 0
Strong duality, an equality you can check: price each binding limit by its shadow price and add them up, (1/7)(45) + (3/7)(27) + (1)(4) = 22, the very objective the primal walk reached at (9, 9, 4). Maximum profit equals the total worth of the resources.
At the best corner the Mind turns the question inside out. It stops asking how to fill the hold and asks instead what one more gram of each resource would buy if it could be had, and which resources are already worth nothing at the margin.
Each resource answers with its shadow price, its dual value: at this optimum one more chargrid hour is worth 1/7, one more unit of hull-frame stock is worth 3/7, and one more crystal-chamber slot is worth a full 1, while the antimatter budget and stabilizer mass, both with room to spare, are worth 0. The ship earns its name here: a shadow price is a marginal utility.
Section 05 · The playground
The worst case, built on purpose
On a log scale the worst case is a straight climb, doubling with every dimension; the little cube on the right is one rung of it.
At n = 3, worst-case Dantzig visits 8 corners; at n = 200 that is 1.606938e60, a number with 61 digits.
All 8 corners visited; optimum (0, 0, 10000), objective 10000.
The chart and every readout above already say it: all 8 corners.
The only thing left to wager is whether you believed a manifold could really drag the greedy rule across every last corner before the exit at (0, 0, 10000). The rig did.
Dantzig visits all 8 corners of the 3D cube; the same construction at n = 200 forces about 2200 pivots.
A smaller, meaner trap sits one rule change away. Read the very same tableau two ways: a naive tie-break loops forever, while Bland's rule walks out.
Naive tie-break: the basis returns to pivot 0's basis every six pivots, a closed loop that never escapes.
The naive lane never leaves this loop: 31 recorded pivots, every basis a repeat of the one six pivots earlier, the objective pinned at 0.
Objective per pivot, the secondary read: both lanes sit at 0 until Bland breaks out to 1.
Corner Case was built to visit corners. Someone, it seems, has now built the corners for it: this cargo manifold is skewed just enough that the drone's own greedy instinct drags it across every last vertex before the exit shows itself, and only the manifest knows whose gift it was.
The manifold is the same cargo bay, its limits skewed on purpose: maximize 100 x1 + 10 x2 + x3 under three tilted limits, and Dantzig's rule marches through all 2³ = 8 corners before it lands at (0, 0, 10000). Stretch the same construction to n = 200 and the tour runs to about 2 to the 200 pivots.
So why is simplex still the workhorse? Because a manifold this hostile has to be built on purpose. On the average case, and on the programs shipping crews actually solve, the greedy rule finishes in a handful of pivots. When a program is large enough to fear the worst case, the interior-point method the next section races takes a different road to the same optimum. The worst case is not rare, it is constructed.
Section 06 · Applications and the race
Networks and the race
A network flow and a linear program are the same eight numbers; hover or focus an edge to light its column in the matrix.
| fsa | fsbcut | faccut | fda | fbd | fcb | fct | fdt | = | |
|---|---|---|---|---|---|---|---|---|---|
| max | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | |
| flow | 6 | 2 | 6 | 0 | 4 | 2 | 4 | 4 | |
| cap | 8 | 2 | 6 | 3 | 5 | 2 | 4 | 5 | |
| net a | 1 | 0 | -1 | 1 | 0 | 0 | 0 | 0 | 0 |
| net b | 0 | 1 | 0 | 0 | -1 | 1 | 0 | 0 | 0 |
| net c | 0 | 0 | 1 | 0 | 0 | -1 | -1 | 0 | 0 |
| net d | 0 | 0 | 0 | -1 | 1 | 0 | 0 | -1 | 0 |
Maximum flow s to t is 8 units, equal to the minimum cut. The cut crosses s to b and a to c. Saturated arcs: s to b, a to c, c to b, c to t.
| edge | da | db | dt | ≤ |
|---|---|---|---|---|
| s→aroute | 1 | 0 | 0 | 1 |
| s→b | 0 | 1 | 0 | 4 |
| a→broute | -1 | 1 | 0 | 2 |
| a→t | -1 | 0 | 1 | 6 |
| b→troute | 0 | -1 | 1 | 1 |
Shortest route s to a to b to t has length dt = 4. Node potentials ds 0, da 1, db 3, dt 4. Binding edges: s to a, a to b, b to t.
One polytope, two racers; scrub the slider to send Corner Case corner to corner along the boundary while Strictly Feasible threads the interior.
- Corner Case, the boundary walk (recorded)
- Strictly Feasible, the interior central path (recorded)
Recorded on both sides: Corner Case replays the boundary walk, Strictly Feasible replays the interior central path (all 24 logged points, mu from 45 toward zero) to the shared arrival (9, 9, 4). Neither is a live solve.
Corner Case at corner 2 of 4 (12, 3, 0); Strictly Feasible in the interior, mu = 0.098, heading to (9, 9, 4).
The same drone that walked the cargo hold is loaned to the fleet, plotting shuttle courses one shift and balancing relay traffic the next. A sleeker vessel has watched the whole tour without once touching a wall. Strictly Feasible means to prove that the long way round the boundary, corner after corner, was never the only way home.
On the very cargo polytope from Section 03, an interior-point method never works the boundary. Instead of stepping corner to corner the way Corner Case does, it follows a path that threads the interior and bends toward the optimum, and every point it passes lies strictly inside every limit, which is exactly what its pilot is named for. Simplex takes the corners and the interior method takes the middle; the interior track above is the recorded central path, replayed as the barrier parameter mu falls toward zero rather than solved live in your browser. Both network figures are linear programs in different clothes: read as node potentials a graph gives a shortest route of dt = 4, and read as arc capacities a network pushes a maximum flow of 8[3].
The rival threads the interior and converges on the same corner without touching a wall. Different style, same arrival.
Section 07 · The engine room
The same walk, twice
Everything above ran twice before it reached this page. A pure-Python reference wrote the traces the figures replay; the same solver, written again in Rust, re-solves live in the browser when a constraint is dragged; and the parity suite pins the two to identical pivot sequences, corner for corner. With the mathematics settled between them, one engineering question is left: what does the identical walk cost in each? For every program on this page, the answer is nothing a reader could feel. The fab-bay program costs 8.1 microseconds in pure Python and Klee-Minty's little cube costs 25.5; the Rust core does the fab bay's work in half a microsecond, and nobody watching this page can tell those apart.
The difference is real; it lives at sizes this page never visits. To measure it without fooling anyone, the harness draws seeded product-mix programs, every coefficient positive and every row a le limit, so the origin is feasible and the region is bounded by construction, in squares from 4×4 up to 192×192. Each instance passes a parity gate before any clock starts: same status, same pivot count, objectives within 1e-6 across engines, so a timing difference can only be a runtime difference. Times are medians over batched samples with the warmup discarded and the garbage collector left on, all on one disclosed machine, an Apple M4 Max. The whole run is committed to the repository as bench/results.json, which is what the badge under each chart means: the numbers replay that committed record.
One walk, four runtimes; the pivot sequences are identical by construction, so the vertical gaps are pure implementation cost.
At 192×192 the same walk costs 461 ms in pure Python, 6.9 ms through the native call, 6.2 ms for the core alone, and 10.3 ms in the browser build, medians across three seeded instances.
Both engines walk the same corners, so both lines climb together; what grows is the space between them. The mechanism fits in a sentence: a pivot touches every cell of the tableau, an interpreter charges tens of nanoseconds per touch to unbox, dispatch, and rebox each float, and a compiled loop charges about one. Cells grow quadratically while the charges hold, so the ratio climbs toward the raw per-cell gap. The two Rust curves tell the opposite story: they start almost 9× apart and end 13 percent apart, because what separates them is not work but a border, and the border grows far more slowly than the solve it wraps.
That border deserves its own figure. The native call reads the LinearProgram dataclass attribute by attribute, converts each row, and builds a real Solution object on the way back. That toll grows with the payload, 4.5 microseconds on the fab bay, 13 on max flow's twelve rows, near 800 at 192×192, but it grows like the problem's size while the solve grows like the problem's work, so the crossing dominates small calls and fades inside big ones; PyO3's guide gives the same advice from the other side, cross the boundary rarely and carry more per crossing[7]. On the fab bay the full native call is 5.0 microseconds: 0.5 of solve wrapped in 4.5 of border. At this page's scale you are timing the border, not the solver.
Every program on this page, timed; the native bar is almost entirely border crossing.
The walk inside never reaches 3 microseconds on any program this page poses; everything else in the native bar is the crossing.
The browser pays the same kind of toll in a different currency. solve_json crosses its border as JSON text, serialized both ways on every call, and still lands within 1.7× of the in-process core at 192×192, in line with the 1.45× to 1.55× average measured for WebAssembly against native code[8], with the JSON on top. Three fences belong around these numbers. They come from one machine and one instance family, dense phase-2-only walks; a program that needs artificial variables would tax every engine more, in roughly the same proportions. The Rust times come from the shipped build, whose release profile is sized for the 500 KB wasm budget (opt-level = "z"). And none of it touches Section 05's lesson: sixty-six times faster is six more dimensions of the hostile bay, 2⁶ is 64, before the walk is exactly as lost as before. The escape there came from a better pivot rule; a faster hull just moves the same wall six dimensions out. So choose the engine the way this page does, the reference for reading, the core for volume, and either one for anything a human is watching, because at human scale both finished long before the frame drew.
Back matter
References
Every fixture optimum on this page is cross-checked against scipy's HiGHS solver (scipy.optimize.linprog(method="highs"), which minimizes, so we negate the objective to maximize), and the oracle badge above links to exactly how that check runs. Two solvers stand behind the figures: the reference solver wrote every committed trace corner for corner, HiGHS independently confirms each optimum, and the live panels re-solve the same simplex core, written in Rust and compiled to WebAssembly[6], in your browser when you drag the hero's limits or push the what-if in Section 03, landing on the very corners the traces already recorded.
max c · x = -min ( -c · x )
Sources
The works the sections lean on, numbered in the order they first appear above.
- G. B. Dantzig, Linear Programming and Extensions. Princeton University Press, 1963. Source behind the cold open's nine-clerk diet run; Dantzig devised the simplex method in 1947.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms. MIT Press. Chapter 29 (linear programming) and section 28.1 (Gaussian elimination, the row reduction each simplex pivot performs); the fab-bay program of Sections 01 and 02 is the classic two-variable product-mix exercise. MIT Press.
- D. Suthers, "Linear programming," ICS 311 Topic 21 lecture notes, University of Hawaii, fall 2020. Source of the worked cargo program walked in Section 03 and the network formulations of Section 06. Topic 21 notes.
- V. Klee and G. Minty, "How good is the simplex algorithm?," in Inequalities III, O. Shisha, Ed. Academic Press, 1972. The skewed cube of Section 05, whose corners a greedy pivot rule is lured through in full.
- V. Chvatal, Linear Programming. W. H. Freeman, 1983. The small degenerate program of Section 05 whose naive tie-break cycles, and Bland's rule as the finite escape.
- minilp: a pure-Rust linear programming solver. crates.io. Prior art for a small, embeddable simplex, and a useful cross-reference for this core. minilp on crates.io.
- PyO3 Contributors, "Performance," The PyO3 user guide. Source for the costs of crossing the Python-Rust boundary and the advice Section 07 quotes: cross rarely, carry more per crossing. pyo3.rs/main/performance.
- A. Jangda, B. Powers, E. D. Berger, and A. Guha, "Not So Fast: Analyzing the Performance of WebAssembly vs. Native Code," USENIX Annual Technical Conference, 2019. Source for the 1.45× to 1.55× average WebAssembly-against-native slowdown Section 07 compares its browser build to. USENIX ATC '19.
Figures draw with d3 version 7, and with scripts on KaTeX 0.16 typesets the static display blocks and the identity above while the interactive panels write plain text so they can rewrite live; both libraries are committed under docs/vendor/ and served exactly as vendored, with no CDN, no bundler, and no build step. Source and MIT license live in the repository, built buildless from hand-written HTML, one stylesheet, and ES modules: github.com/nilesh-patil/feasible-region.
Appendix A
The glossary
The working words of the walk, each defined in a sentence; the eight underlined terms above reveal these same definitions on hover or keyboard focus, and two more, reduced cost and rhs, live here alone.
- Tableau The grid of coefficients a solver pivots on, one row per constraint above a row for the objective.
- Basis The set of variables held nonzero at a corner, one for each row of the tableau.
- Entering The variable a pivot brings into the basis, the column chosen to grow.
- Leaving The variable a pivot sends out of the basis, the row that reaches zero first.
- Primal The original program, maximizing the objective under the resource limits.
- Dual The shadow price on each constraint, what one more unit of that resource is worth to the objective.
- x* The optimal point a solver returns, the corner where the objective reaches its best value.
- mu The barrier parameter an interior path drives toward zero as it approaches the optimum.
- Reduced cost How much the objective would improve per unit if a variable currently out of the basis were brought in.
- rhs The right-hand side column of the tableau, the amount of each resource its constraint still allows.
Appendix B
The concept map
Every idea the page builds, gathered in one place, each named and defined in a sentence and linked to the section and figure where it lives.
- The set of points that satisfy every constraint at once, the shaded area a solver is free to search.
- A point where enough constraints meet to pin it in place, and where an optimum can always be found.
- The linear quantity being maximized, drawn as an arrow pointing the way the score grows.
- The room left under an at-most limit, added as its own variable so the limit reads as an exact equation.
- The grid of coefficients a solver pivots on, one row per constraint above a row for the objective.
- The set of variables held nonzero at a corner, one for each row of the tableau.
- The variable a pivot brings into the basis, the column chosen to grow.
- The variable a pivot sends out of the basis, the row that reaches zero first.
-
Infeasible After Sec. 03 Fig. 5A program whose limits leave no point that satisfies them all, so the solver reports that no plan exists.
- The original program, maximizing the objective under the resource limits.
- The shadow price on each constraint, what one more unit of that resource is worth to the objective.
- The best primal value and the best dual value meet at one number, each certifying the other.
- How the pivot count grows with problem size, a built worst case against the handful of steps a typical program needs.
- A pivot rule returning to a basis it already held, so the walk loops without ever improving.
- The lowest-index tie-break that keeps the walk finite, though not that it is fast.
- The barrier parameter an interior path drives toward zero as it approaches the optimum.
- Section 04's strong duality on a network, where the largest flow equals the lightest cut.
- The toll a problem pays to move between runtimes, in attribute reads at the PyO3 boundary and in JSON at the browser's, and nearly the whole bill on a small program.