Linear programming

The field’s workhorse, and until now missing from a spoke of 36 metaheuristic pages. T2 — Wikipedia as a tertiary survey, matching this spoke’s existing practice (wikipedia-convex-optimization and the rest); the free text chapters that would be T1 were not reachable, which is recorded on this spoke’s growth edge.

The problem. Maximize cᵀx subject to Ax ≤ b, x ≥ 0 — “the optimization of a linear objective function, subject to linear equality and linear inequality constraints.” The constraints carve out a convex polytope, “the intersection of finitely many half spaces,” and because the objective is linear an optimum sits at a vertex. That single geometric fact is why LP is tractable and why it is nothing like the landscapes the rest of this spoke searches.

The algorithms

• Simplex (Dantzig, 1947): start at a feasible vertex and “walk along a path on the edges of the polytope to vertices with non-decreasing values of the objective function.” Fast in practice, exponential in the worst case — Klee and Minty built the counterexamples — and whether a simplex variant runs in polynomial time is still open.
• Ellipsoid (Khachiyan, 1979): the first proof that LP is solvable in polynomial time. LP is in P, however badly simplex behaves.
• Interior point (Karmarkar, 1984): polynomial and practical, the reason large LPs are solved by two different families of method today.

Duality. Every LP has a dual whose feasible values bound the primal, and strong duality makes the bound exact: “if the primal has an optimal solution, x*, then the dual also has an optimal solution, y*, and cᵀx* = bᵀy*.” A solution therefore arrives with a certificate. Nothing in this spoke’s metaheuristic half has an equivalent — genetic-algorithm or particle-swarm-optimization return a point and no proof that anything better does not exist.

Why this page changes the spoke’s frame

no-free-lunch-theorem says no search method beats another averaged over all problems, and the metaheuristic literature here treats that as licence for the field’s variety. LP is the standing reminder of the other half of the argument: when a problem has exploitable structure, exploit it. Linearity plus convexity buys a global optimum, a polynomial-time guarantee and a duality certificate — everything a black-box search gives up. The interesting question the spoke should be asking is not which metaheuristic wins, but when a problem is a disguised LP.

Applications named: transportation, energy, telecommunications, manufacturing; planning, routing, scheduling, assignment, design. Related: integer-programming, convex-optimization.