Linear Programming from Scratch — The Workhorse of Optimization

The oldest and most widely deployed tool for choosing the best option under limited stock, budget and time. From the three-part recipe for writing a model down, to why the answer always sits at a corner, to what duality tells you a kilo of flour is really worth — built up from zero.

A bakery, and the best way to use what's on the shelf

Picture a small bakery. Today's stock is 10 kg of flour, 3 kg of butter, and 8 hours of oven time. You can bake two things: sandwich loaves and croissants. How many of each should you make to earn the most today?

Say croissants earn more per kilo of ingredients, so you go all-croissant — now the butter runs out first. Go all-loaf instead and the oven time doesn't stretch far enough. Which resource runs out first changes depending on the mix you choose. That's why no single metric decides this for you.

And yet every calculation in the problem is nothing but addition and multiplication by a constant. Double the loaves and you exactly double both the flour consumed and the profit earned. Bake both and the consumption is just the sum of the two. A problem shaped like this is a linear program (LP), and factories, freight networks and ad-serving systems all over the world still run on this framework today.

What exactly is "linear" here

Writing a model down is always the same three-part recipe: decision variables (the numbers you get to choose), an objective function (the value you want to push up, or down), and constraints (the inequalities you must respect). And "linear" means the objective and every constraint can be written using nothing but constants times variables, added together. No $x^2$, no $\sin x$, no $x_1x_2$.

That's a strong assumption, and reality breaks it constantly: bulk discounts lower the unit price (economies of scale), switching the oven between loaves and croissants costs 20 minutes (changeover), and you can't bake 3.7 croissants (integrality). So the first job is always to judge whether the thing can be written linearly at all. If it can, an entire toolkit that handles tens of thousands of variables opens up. If it can't, you need a different framework.

Writing one down: splitting an ad budget

Here's a more modern version. You have a ¥1M budget this month to split across search, social and video. Conversions per ¥10k are 12, 8 and 5 respectively; each channel can absorb at most ¥400k, ¥600k and ¥800k; and for brand reasons you want at least ¥100k going into video.

Let the decision variables be the spend on each channel, $x_1,x_2,x_3$ (in units of ¥10k). The objective is $12x_1+8x_2+5x_3$; the constraints are $x_1+x_2+x_3\le100$, the per-channel caps, $x_3\ge10$, and everything $\ge0$. That's the whole model. The general form always collapses into a single line.

Reading the symbols one at a time: $x$ is the column vector of decision variables. $c$ holds the value of one unit of each variable (12, 8, 5). $c^\top x$ multiplies them out and sums — total conversions. $A$ is the table of coefficients on the left-hand side of the constraints, $b$ is the vector of limits, and $Ax\le b$ is shorthand for "satisfy every constraint at once". $x\ge0$ is the obvious condition that you can't spend a negative budget. So equation (1) says nothing more than: "respect every cap, and pick the allocation whose total value is largest."

The objective $c^\top x$ is literally a dot product, and a dot product measures how well two vectors' directions agree. So linear programming can be restated as: find the point inside the allowed region whose direction lines up best with $c$. That reframing pays off directly in the simplex method below.

Geometry: the answer always sits at a corner

Draw the two-variable case on paper. A constraint like $x_1+x_2\le100$ is a half-plane — everything below a line. Stack every constraint and you get a polygon bounded by straight lines (a polyhedron in three variables), called the feasible region.

Meanwhile the contour $c^\top x = \text{const}$ is itself a straight line, and changing the constant doesn't tilt it — it just slides it sideways. So optimization becomes: push a ruler, kept parallel to itself, as far as it will go in the direction of $c$ without leaving the polygon. The last place a parallel line touches a convex polygon is always either a vertex or an entire edge.

Which means: if an optimal solution exists at all, there is an optimal solution at a vertex (the fundamental theorem of linear programming). A search over infinitely many points has just collapsed into a search over finitely many corners — that is the entire reason LPs are solvable.

Enumerating them all is still hopeless, though. With $n$ variables and $m$ constraints, the number of candidate vertices (basic solutions) is up to $\binom{n}{m}$. Even a modest problem with 40 variables and 20 constraints gives $\binom{40}{20}\approx1.4\times10^{11}$, and a supply-planning model runs to tens of thousands or millions of variables.

How to read Big-O notation is covered in Computational Complexity from Scratch. The one conclusion needed here: you need a smart way to walk.