Appearance
10.5 — Linear Programming
A refinery buys crude oil of several grades and produces petrol, diesel and jet fuel. Each grade yields different proportions, each product sells at a different price, each processing unit has a capacity limit, and contracts specify minimum deliveries. What should it buy and produce this month?
Every quantity is a variable, every capacity is an inequality, and profit is a sum of prices times quantities. When the objective and all the constraints are linear, the problem is a linear program, and it can be solved exactly, at enormous scale, with a guarantee of optimality.
That combination — real problems, exact answers, huge scale — is why linear programming is probably the most economically valuable piece of mathematics of the twentieth century.
1. The standard form
\text{maximise } \mathbf{c}^\mathsf{T}\mathbf{x} \quad\text{subject to}\quad A\mathbf{x}\le\mathbf{b}, \quad \mathbf{x}\ge0
\mathbf{c} holds the profit per unit, A the resource requirements, \mathbf{b} the resource availability. Minimising a cost is the same problem with the signs flipped.
Chapter 2.4's workshop problem was a small one. Chairs and tables, limited by wood and labour:
\text{maximise } 300x+500y \quad\text{s.t.}\quad x+y\le10,\;\; 2x+y\le16,\;\; x,y\ge0
2. Why the answer is always at a corner
Each inequality cuts the space with a flat boundary. Together they enclose a feasible region — a convex polyhedron, meaning a shape with flat faces and no dents.
The objective's contours are parallel flat surfaces, since the objective is linear. Slide them across the region in the improving direction, and the last point of contact before leaving is always a vertex — or, in a tie, an entire edge or face, which still includes vertices.
So you never need to search the interior. That single fact reduces an infinite search to a finite one, and it is what makes linear programming tractable.
3. The simplex method
George Dantzig developed it in 1947 for US Air Force planning problems. The idea follows directly from Section 2:
Start at a feasible corner. Look at the neighbouring corners along the edges. If any improves the objective, move there. Repeat until no neighbour is better.
Because the region is convex, a corner with no better neighbour is globally optimal — there is no possibility of a local optimum elsewhere. That guarantee is the payoff of convexity from Chapter 10.4.
On the workshop problem: start at (0,0) with profit 0. Moving along the y axis to (0,10) gives 5,000. Neighbouring corner (6,4) gives 1800+2000 = 3800, which is worse. So (0,10) is optimal — 10 tables, no chairs, ₹5,000.
The strangest complexity result in computing
In the worst case, the simplex method is exponential. Klee and Minty constructed a problem in 1972 where it visits every one of 2^n vertices.
In practice it is essentially always fast — typically a small multiple of the number of constraints, and it routinely solves problems with millions of variables.
The gap between worst case and practice is enormous and not fully explained, though smoothed analysis — showing that random perturbations of any problem are solved quickly — goes a long way. It is the standard example that worst-case complexity can be a poor guide to what will actually happen, and Volume I, 4.1 makes the same point about quicksort.
Interior point methods, from Karmarkar in 1984, take a different route: cut through the interior of the region towards the optimum rather than walking the edges. They have polynomial worst-case guarantees and are faster on very large sparse problems. Modern solvers include both and choose, since neither dominates.
4. Duality
Every linear program has a partner, its dual, and the relationship is the most useful theoretical result in the subject.
The workshop's primal problem asks: how much of each product should we make to maximise profit?
The dual asks: what is each resource worth? Assign a price to each unit of wood and each labour hour such that the total value of the resources is minimised, subject to those prices being high enough that no product looks underpriced.
Strong duality: the two problems have the same optimal value. The maximum profit achievable equals the minimum value of the resources consumed.
The dual variables are the shadow prices — the same quantity as the Lagrange multipliers of Chapter 5.7. Each one says how much extra profit one more unit of that resource would produce.
This is what a manager actually needs. The primal says what to make; the dual says which constraint is costing you money and therefore where to invest. If wood has a shadow price of ₹200 per unit and labour has zero, buying more wood is worth up to ₹200 per unit and hiring more labour is worth nothing, because you are not running out of labour.
Complementary slackness makes it sharp: a resource that is not fully used has a shadow price of zero, and a resource with a positive shadow price is fully used. Only binding constraints have value.
5. Integer programming, and why it is much harder
Add the requirement that variables be whole numbers — you cannot build 3.7 aircraft or send 0.4 of a lorry — and the problem becomes integer programming.
This is NP-hard, unlike linear programming, and the reason is that the corners of the feasible region are generally not at integer points, so the geometric argument of Section 2 collapses.
And rounding does not work. Rounding an optimal fractional solution can give an answer that is infeasible, or feasible but far from optimal. This is not a rare edge case; it is typical.
What actually solves them: branch and bound. Solve the relaxed problem without the integer requirement. If the answer happens to be integral, you are done. Otherwise pick a fractional variable, split into two subproblems — one with that variable forced up, one forced down — and recurse. The relaxed solution gives a bound, so any branch whose bound is worse than the best integer solution found so far can be discarded without exploring it.
Combined with cutting planes, which add constraints that exclude fractional solutions without excluding integer ones, modern solvers handle remarkably large integer programs. They also occasionally take forever on small ones, and predicting which is difficult.
Where integer variables are essential: yes/no decisions (open this warehouse or not), assignments (this crew to this flight), sequences (visit cities in this order). These are the problems that matter most in logistics, and they are exactly the hard ones.
6. Where it actually runs
Airline crew scheduling. Assign crews to flights obeying rest rules, qualifications, base locations and union agreements, at minimum cost. One of the largest optimisation problems solved routinely, and worth hundreds of millions per airline per year.
Diet and blend problems. The original 1940s application computed a minimum-cost diet meeting nutritional requirements. The mathematically optimal answer was famously unpalatable, which is a lesson about objective functions: the solver optimises exactly what you asked for, so if palatability matters it must be in the model.
Refinery and chemical blending. Almost every refinery in the world runs a linear program to decide its production, updated continuously as prices move.
Transportation and logistics. Which warehouse serves which customer, which lorry takes which route.
Power grid dispatch. Which generators run at what output, minute by minute, minimising cost subject to demand, transmission limits and reserve requirements. The resulting shadow prices on the demand constraints are the wholesale electricity prices, computed by a solver and used for actual settlement.
Portfolio optimisation. Markowitz's model minimises risk for a required return, subject to allocation constraints. Quadratic rather than linear, and convex, so the same theory applies.
Support vector machines, in machine learning, are a quadratic program with linear constraints. Before deep learning they were the best general classifier available, and their training is exactly this chapter's machinery.
7. The honest limits
Linearity is an assumption, and often a false one. Real costs have economies of scale, real yields are nonlinear, real demand responds to price. Linear programming approximates, and the approximation is sometimes good and sometimes not. Piecewise-linear approximation extends the reach, at the cost of more variables.
The data must be right. A solver gives the exact optimum of the model you gave it. If the cost coefficients are guesses, the answer is an exact optimum of a wrong problem, and its precision is misleading. Sensitivity analysis — how much can each coefficient change before the solution changes? — matters more than the solution itself, and every solver reports it.
The objective must be the real one. Minimising cost while ignoring reliability, or maximising throughput while ignoring fairness, gives an answer that is optimal and unusable. This is the diet problem's lesson, and it is the same failure mode as an AI system optimising a proxy for what you actually wanted — Volume I, 12.10.
Every formula above, built from scratch
None of the results in this chapter are worth memorising, because each one can be rebuilt in under a minute from something simpler. What follows is that rebuilding, one result at a time, so the formula and the reason for it sit on the same page as the explanation that needed them.
Linear programming
\text{maximise } \mathbf{c}^T\mathbf{x} \quad \text{subject to } A\mathbf{x}\le\mathbf{b},\ \mathbf{x}\ge0
The fundamental theorem. The feasible region is a convex polygon (or its higher-dimensional version), and a linear objective has no interior turning points — its gradient is constant and never zero. So the optimum is always at a corner, and the search reduces from an infinite region to a finite list of vertices.
The simplex method walks from corner to neighbouring corner, always improving, until no neighbour is better. Since the region is convex, no better corner exists anywhere at that point. It is exponential in the worst case and extremely fast in practice — one of the great unexplained gaps in computing.
Duality.
\text{minimise } \mathbf{b}^T\mathbf{y} \quad\text{subject to } A^T\mathbf{y}\ge\mathbf{c},\ \mathbf{y}\ge0
\mathbf{c}^T\mathbf{x}^* = \mathbf{b}^T\mathbf{y}^*
Every maximisation problem has a matching minimisation problem with the same optimal value. The dual variables y_i are shadow prices: y_i is exactly how much the objective would improve if constraint i were relaxed by one unit. That is the number a manager actually wants — not "make 40 of product A" but "an extra hour of machine time is worth £12, and an extra kilo of material is worth nothing."
8. Where this shows up in your life
Every flight you take. The crew, the aircraft assignment and the schedule came from a solver.
Every parcel delivery route.
Every unit of electricity you use, and the price it was settled at.
Every fuel you buy. The refinery's production plan.
Every spreadsheet Solver button. Excel's Solver is a linear and nonlinear programming engine, and the constraints you type are Section 1's inequalities.
Part 10 is finished, and with it the working mathematics of this volume. What remains is the part that is not a tool at all — the people, the problems that resisted for centuries, and the discovery that mathematics has limits it cannot argue its way past.
More places these turn up
Floating point is why a spreadsheet occasionally shows -2.8\times10^{-17} instead of zero, and why financial systems store money in whole pence rather than in doubles. Newton's method is inside the square-root button you have pressed a thousand times. Runge–Kutta is integrating the equations behind the weather forecast you checked this morning, and the same method flies spacecraft. Gradient descent trained every model you have interacted with today. And linear programming, with its shadow prices, routes the delivery van, schedules the airline crew and blends the petrol in your tank.
Next: 10.P — Worked Problems runs each algorithm by hand, iteration by iteration, so you can see the digits appear.