Linear Programming: How a 70-Year-Old Algorithm Powers Modern Operations
The optimization problem behind everything
Every day, somewhere in the world, an airline figures out how to route 6,000 flights with 4,000 crew members while respecting union rules and minimizing fuel burn. A refinery decides how to blend twelve crude streams into eight finished products to maximize margin. A meat plant works out which cuts to make from today's carcasses to fill the order book at the highest profit.
These problems all look different on the surface. Underneath, they're the same shape: choose values for many decision variables, satisfy a long list of constraints, and make a target as good as possible. That shape has a name — linear programming — and an algorithm has been quietly solving it since 1947.
What "linear" actually means
An LP has three ingredients:
- Decision variables — what you're choosing (lb of Ribeye to fabricate, gallons to ship, hours to schedule)
- Constraints — what you can't violate (capacity, demand, yield ratios, freshness windows)
- An objective — what you're maximizing or minimizing (margin, cost, time)
"Linear" means the relationships are first-degree: 1 lb of carcass yields 0.6 lb of trim, period — no x², no curves, no exponentials. That's a real restriction, but it's also why LP is so fast. The math has a clean geometric interpretation: the feasible region is a many-sided polytope, and the optimum is always at a corner of it.
A toy example
Suppose you can make two products, A and B. Each unit of A takes 2 hours of labor and earns $30 margin. Each unit of B takes 3 hours and earns $50. You have 60 hours of labor available. How many of each should you make?
Try it by hand: 30 of A gives $900. 20 of B gives $1,000. Mix 15 of A with 10 of B and you've used 60 hours for $950. There's a best answer, and brute force will find it — eventually.
An LP solver finds it instantly. With two variables you barely notice. With six thousand variables and five hundred constraints — which is what a real production plan looks like — brute force takes longer than the heat death of the universe. LP takes 87 milliseconds.
Why it scales
George Dantzig invented the simplex method in 1947. It walks from corner to corner of the feasible region, always moving toward a better objective value, until no neighboring corner is better. In the worst case it's exponential, but in practice it's blindingly fast — most real problems solve in a handful of iterations.
Since then, the field has added interior-point methods (which cut through the middle of the polytope instead of walking the edges) and dual algorithms (which solve a related problem that's sometimes easier). Modern solvers like HiGHS, Gurobi, and CPLEX pick the right method automatically and handle millions of variables on commodity hardware.
Where LP shows up
Most industries you can name use LP somewhere:
- Airlines — crew scheduling, gate assignment, fuel routing
- Refining and chemicals — blend optimization, capacity planning
- Logistics — vehicle routing, warehouse location
- Finance — portfolio rebalancing under constraint
- Energy — grid dispatch, unit commitment
- Telecoms — bandwidth allocation, network routing
- Food processing — fab planning, blend formulation, distribution
If a problem can be phrased as "choose quantities, respect limits, maximize value," LP probably has the answer.
Why production planning fits LP perfectly
Production problems are tailor-made for linear programming:
- Constraints are naturally linear. Yield ratios, shift capacities, drop limits, freshness windows — all linear relationships.
- Optimality matters. The difference between "good enough" and "best" is real money. Across hundreds of shifts a year, the gap compounds.
- Conditions change constantly. Orders come in, prices move, inventory shifts. The plan has to re-solve in seconds, not hours.
- Dual values are useful. LP doesn't just give you the answer — it tells you the marginal cost of every constraint. Where is your bottleneck? What's it worth to relax it? The dual variables answer both.
How MakeSheet uses it
MakeSheet's solver is HiGHS, an open-source LP/MIP solver built by Edinburgh. A typical MakeSheet model has 6,000+ decision variables (one per product × shift × facility) and 500+ constraints. It solves in under 100 milliseconds — fast enough to re-run every time an order changes or a sales rep clicks "Check Availability."
The result is a production plan that's provably optimal under today's conditions, recomputed in real time, with a clean handoff to the books on the other side. A 70-year-old algorithm doing 21st-century operations work.
