The 1947 Algorithm That Routes Every Package You've Ever Received

April 28, 2026·10 min read

In 1947, a young mathematician at the Pentagon named George Dantzig was given the job of mechanizing the Air Force's planning process. The problem was so big it had a name: "programming," in the military sense of scheduling activities. Dantzig wrote down the constraints as linear inequalities, the objective as a linear function, and produced an algorithm that walked from corner to corner of the resulting geometric shape until it found the best one. He called it the simplex method. Almost eighty years later, it is still the algorithm that decides which planes fly which routes, how a refinery blends gasoline this hour, how the grid dispatches power, and how your package got from a warehouse to your door.

Check out the full video on my YouTube channel Divide and Quantum.

What Linear Programming Actually Is

A linear program is the simplest non-trivial optimization problem you can write down. You have:

A vector of decision variables x = (x_1, x_2, ..., x_n), all required to be non-negative.
A linear objective function c^T x that you want to maximize or minimize.
A set of linear constraints A x <= b.

That is it. No squares, no products of variables, no logarithms. Just sums and scalar multiples. The standard form looks like:

maximize    c^T x
subject to  A x <= b
            x   >= 0

The restriction sounds severe. It is not. An enormous fraction of real planning problems either are linear or admit a linear approximation that is good enough to ship. A refinery's blending recipes, an airline's crew schedule, a warehouse's pick lists, a power grid's hourly dispatch, a delivery network's routing, all linear, or close enough.

The Geometry: A Shape With Many Corners

Each constraint a_i^T x <= b_i carves space in half: one side is allowed, the other forbidden. Stacking up many such constraints leaves an intersection of half-spaces called a polytope. In two dimensions it is a polygon. In three, a polyhedron. In a million dimensions, the same idea, just impossible to picture.

The crucial property: a linear objective function attains its maximum on a polytope at a corner (technically a vertex, or extreme point). The interior cannot be optimal, because from any interior point you can always slide a little further in the direction of the objective gradient and improve. The same logic forces the optimum to a corner, not just an edge or a face.

So the optimization collapses into a finite search. There are only finitely many corners. You just need a way to walk through them intelligently.

How the Simplex Method Walks the Corners

Dantzig's algorithm starts at one corner of the polytope and walks along edges, always to a neighbor that improves the objective, until no neighboring corner is better. That neighbor is optimal.

The hard part is doing this without enumerating all the corners (a polytope in n dimensions with m constraints can have on the order of C(m, n) corners, which is astronomical). The simplex method's trick is algebraic:

Represent the current corner by a basis — a choice of n linearly independent constraints that are tight (satisfied with equality) at this corner.
Compute the reduced costs of the non-basic variables. The reduced cost of a variable tells you how much the objective would change if you brought that variable into the basis.
If every reduced cost is non-positive (for a maximization), you are optimal. Stop.
Otherwise, pick a variable with positive reduced cost (Dantzig's original rule: pick the largest). This is the variable to bring into the basis.
Do a ratio test to figure out which variable currently in the basis must leave to keep all variables non-negative. This is the binding constraint along the chosen edge.
Pivot: update the basis, the corner, and the tableau. Go to step 2.

Each pivot is one edge of the polytope. The objective strictly improves at each step (in the absence of degeneracy), so the algorithm cannot revisit a corner and must terminate.

Why It Works So Well In Practice

Here is the strange part. The simplex method has exponential worst-case complexity. Victor Klee and George Minty constructed a polytope in 1972 (the "Klee–Minty cube") where the simplex method, with Dantzig's pivot rule, visits all 2^n corners before terminating. Theoretically, this is as bad as brute force.

In practice, this never happens. Real LPs solve in something like O(m) to O(m^2) pivots, where m is the number of constraints. The reasons are not fully understood, but the empirical record is overwhelming: solvers like CPLEX, Gurobi, and HiGHS routinely crush problems with hundreds of thousands of variables and constraints in seconds. The simplex method is one of the most successful algorithms in history despite an embarrassing worst case.

This gap between theory and practice has been a major driver of research into smoothed analysis (Spielman and Teng, 2001), which proved that the simplex method runs in polynomial expected time under small random perturbations of the input. That is currently the best explanation we have for why it works as well as it does.

Interior Point Methods: The Other Way

In 1984, Narendra Karmarkar at Bell Labs published an algorithm that solves LPs in polynomial worst-case time by, instead of walking the corners, cutting through the interior of the polytope along a "central path." This launched the field of interior point methods, which today are the algorithm of choice for very large LPs and the only practical option for related problems like semidefinite programs.

Modern solvers carry both simplex and interior point implementations and pick between them based on problem structure. Simplex is faster on smaller problems and lets you "warm start" from a previous solution (priceless when you are re-solving a slightly modified LP every minute, as airlines do). Interior point scales better to enormous problems and is more parallelizable.

A Concrete Example: The Diet Problem

The textbook example is the diet problem, which is also one of the first real applications of LP (Stigler, 1945). You have a list of foods, each with a cost per unit and a nutritional profile. You want to satisfy your daily requirements for protein, fat, carbs, vitamins, and so on, while spending the least money.

Let x_i be the amount of food i you buy. Then:

minimize    sum_i  cost_i * x_i
subject to  sum_i  nutrient_ij * x_i  >=  requirement_j   for each nutrient j
            x_i >= 0

Here is a small Python implementation using scipy.optimize.linprog:

python
import numpy as np
from scipy.optimize import linprog

# Foods: oats, chicken, broccoli, peanut butter
foods = ['oats', 'chicken', 'broccoli', 'peanut_butter']
cost = [0.05, 0.40, 0.10, 0.15]  # dollars per 100g

# Nutrients per 100g of each food
#                 oats  chicken  broccoli  pb
calories       = [389,   165,     34,      588]
protein_g      = [16.9,  31.0,    2.8,     25.0]
fat_g          = [6.9,   3.6,     0.4,     50.0]
carbs_g        = [66.3,  0.0,     6.6,     20.0]

# Daily requirements (minimums)
req_calories = 2000
req_protein  = 75
req_fat      = 55
req_carbs    = 250

# linprog minimizes c^T x, with A_ub @ x <= b_ub.
# We have *minimum* requirements, so we negate to flip the inequality:
#   sum(nutrient * x) >= requirement
#   -> -sum(nutrient * x) <= -requirement
A_ub = -np.array([calories, protein_g, fat_g, carbs_g])
b_ub = -np.array([req_calories, req_protein, req_fat, req_carbs])

# Solve
result = linprog(c=cost, A_ub=A_ub, b_ub=b_ub, method='highs')

if result.success:
    print(f"Minimum daily cost: ${result.fun:.2f}")
    for food, amount in zip(foods, result.x):
        if amount > 1e-6:
            print(f"  {food}: {amount * 100:.0f} g")
else:
    print("No feasible diet found.")

Run it and you will get a wildly unappetizing answer (Stigler's original 1945 solution called for 370 lbs of wheat flour and 57 cans of evaporated milk per year). That is the point: LP finds the mathematically optimal solution, which is rarely the humanly optimal solution. Real diet problems add palatability constraints, variety constraints, and shadow constraints for things like "no more than 200g of any single food per day." This is how LP is used in practice: a kernel of cost minimization wrapped in dozens of judgmental constraints that encode what the modeler actually cares about.

Where It Actually Runs

Airlines

Crew scheduling, fleet assignment, and revenue management are all LPs (or integer programs built on LPs). When American Airlines re-solves its crew pairings, it is solving an LP with millions of variables. The annual savings from running these models correctly are measured in the hundreds of millions of dollars.

Oil Refineries

The product slate of a refinery — how much gasoline of which grade, how much diesel, how much jet fuel — changes hour by hour with crude prices and demand. The blending recipes that hit specs at minimum cost are computed by LPs running on the plant control system. Refineries that adopted LP-based blending in the 1950s and 60s ate the ones that did not.

Power Grids

Every five to fifteen minutes, the operator of a power grid solves an "economic dispatch" LP that decides which generators run at what output to meet demand at minimum cost subject to transmission constraints. ERCOT, PJM, MISO, and the European TSOs all do this. When you hear about "negative electricity prices" during a storm, those are LP shadow prices doing their job.

Package Routing

The line haul network for FedEx, UPS, and Amazon — the trucks and planes that move parcels between hubs — is planned by mixed-integer programs whose LP relaxations are solved millions of times during the search. The same is true of last-mile vehicle routing, which is a much harder problem (vehicle routing is NP-hard), but most modern solvers attack it with LP-based bounding.

Telecommunications

Bandwidth allocation in carrier networks, optical wavelength assignment, and CDN cache placement are all LPs or LP-relaxations of integer programs.

Limitations and What Comes Next

Integrality

The big one. Many real decisions are yes/no or count-based: assign this flight to this crew or not, ship via this truck or not, open this warehouse or not. These require variables that take integer values, which turns the problem into integer linear programming (ILP) or mixed-integer linear programming (MILP). ILP is NP-hard. The standard attack is branch and bound, which solves a sequence of LP relaxations to derive bounds and prune the search tree. The LP solver is the engine; the integer logic is the chassis.

Nonlinearity

Real systems are not exactly linear. Power flow on an AC grid is governed by quadratic equations, not linear ones. Refinery yields curve nonlinearly with feed composition. Practitioners handle this with piecewise linear approximations (lots of small LPs), with successive linear programming (repeatedly linearize, solve, update), or by stepping up to convex optimization or nonlinear programming entirely.

Uncertainty

LP gives you the optimal plan for the data you typed in. Real data is noisy, and the optimal plan for the wrong data can be catastrophic. Stochastic programming and robust optimization are the principled responses, both of which use LPs as building blocks.

Degeneracy and Cycling

In theory, the simplex method can cycle through a set of degenerate corners forever without improving. In practice, modern solvers use Bland's rule or lexicographic pivoting to guarantee termination, at a small cost in average performance.

The Bigger Picture

Linear programming is one of those rare ideas that turned out to be much more important than its original problem. Dantzig was trying to schedule the Air Force. The mathematical object he defined — minimize a linear function over a polytope — turned out to model a staggering fraction of everything we do at industrial scale. The algorithm he wrote down — walk corner to corner along edges that improve the objective — turned out to work absurdly well despite a terrifying worst case, and to be the kernel of every optimizer that has since been built on top of it.

The next time a package shows up at your door faster than seems physically reasonable, there is a linear program somewhere that decided exactly which truck it rode on, which plane before that, and which hub it passed through. The algorithm is older than most of the people running it. It is still winning.