Optimisation, drawn
Most of this subject is taught as algebra.
Most of it is actually geometry.
Guides to operations research that build the picture first and name it afterwards. Each one is a worked example you can drag around, and every number in the prose is produced by the code beside it, in exact rational arithmetic, checked by tests.
They are numbered in the order they build on each other. The first five are one chain and are best read in sequence; the last stands on its own.
-
Two problems, one number
Every planning problem has a second problem hiding inside it, and solving either one solves both. Built from a workshop with three shelves and two products, ending on what a bottleneck costs you and the narrow range over which that figure holds.
-
Along the edge, or through the middle
In 1972 two mathematicians built a shape to embarrass the standard method for linear programming, and it works: on a squashed cube in ten dimensions the method stops at all 1024 corners. In seventy years of real models nobody has ever met one. Why the bad case is real, why it never happens, and why the method built to dodge it never lands on a corner at all.
-
The machine got wider, not faster
Two runs on the same small problem, from the same start, with the same step sizes, differing by one term in one line. One lands on the right answer. The other swings between $0 and $753 forever. Why linear programming had to change algorithms when machines started getting wider instead of faster.
-
Solving a problem you never wrote down
An order of boards takes seven, and proving that six is impossible is far harder than finding a way to do it in seven. The method that proves it works with one unknown per way of cutting a board — four trillion of them for a real order — and never writes any of them down. Ends on branch-and-price, and the two bugs that produced 476 confident wrong answers before the tests found them.
-
What solvers actually do
Hand a solver a twenty-row model and it deletes thirteen of the rows before any algorithm runs, and settles one of the decisions by arithmetic rather than by searching. What presolve is, why it is where the gap opens, and which solvers you can actually deploy without a licence server ruining your week.
-
The wait is not about the speed
A clerk who gets through the average customer in six minutes will hand someone a wait of an hour without ever slowing down. Little's law as one region measured twice, why variability rather than utilisation does the damage, and a 95% confidence interval that contains the true answer 9% of the time.
In the queue
- Branch and bound, branch and cut
- The tree, and what pruning actually prunes.
- Benders decomposition
- Column generation pointed the other way, producing rows instead of columns.
How these are made
Exact rational arithmetic throughout, so "equal" means equal rather than equal to six decimals. Where a result can be reached by a second route that shares no code with the first, it is: the simplex answers are checked against brute-force vertex enumeration, column generation against solving the full model, branch-and-price against exhaustive integer search.
Figures are generated by scripts, chapters are generated from one source
file, and a test asserts that every number quoted in the prose is still the
number the code produces. make verify checks the lot.