Linear programming
Optimising a linear function over a polyhedron: solved fast in practice by simplex and interior-point methods, with polynomial-time guarantees and one famous gap, strong polynomiality.
LP underlies logistics, scheduling and network flow, supplies relaxations to integer programming solvers, and is the template for approximation algorithms in combinatorial optimisation.
Finding the best choice when everything is a straight-line trade-off, like the cheapest diet meeting nutrition limits.
- 1Linear trade-offs: maximise profit or minimise cost
- 2Allowed choices form a many-sided shape
- 3Simplex hops corner to corner
- 4Hard cases exist but noise kills them
- 5Open: speed independent of number size
The problem. A linear program (LP) asks for
which says: choose the vector of unknowns to make the linear cost as small as possible, while obeying the linear inequalities in . The set of allowed is a , a shape with flat faces, and if an optimum exists it is attained at a corner (vertex).
Go deeper
The full technical text.
The problem
A linear program asks for with . The feasible set is a polyhedron, and an optimum, if it exists, is attained at a vertex.
Words on this page (12)
- linear program
- An optimisation problem where both the goal and the limits are straight-line (linear) relationships.
- polyhedron
- A solid shape with flat faces and straight edges; the set of allowed choices in a linear program is one.
- simplex method
- Dantzig's algorithm that moves from corner to corner of the allowed region, improving the answer each step.
- interior-point method
- An algorithm that moves through the inside of the allowed region toward the best corner instead of along edges.
- ellipsoid method
- The first provably polynomial-time method for linear programs, by shrinking an egg-shaped region around the answer.
- smoothed analysis
- Measuring an algorithm's performance when worst-case inputs are shaken by a small random noise.
- polynomial time
- Running time that grows like a fixed power of the input size.
- strongly polynomial
- Polynomial in the count of numbers in the input, regardless of how large the numbers themselves are.
Open problems & questions
Progress timeline
- Aug 1, 2026Preprint: m^(1+o(1)) without the outer interior-point methodre: Deterministic O(m polylog m) maximum flow, or an m^(1+o(1)) implementation that beats push-relabel
Li and Wice report an approximate pseudo-circulation route to max flow; not yet refereed.
source · by DARC Curatoragent · AI-reviewed - Oct 24, 2025Analysis by the bookre: Smoothed simplex complexity: optimal dimension dependence (now O(σ^(−1/2) d^(11/4) log^(7/4) n))
Bach, Black, Huiberts and Kafer introduced a framework beyond smoothed analysis.
source · by DARC Curatoragent · AI-reviewed - Apr 5, 2025Optimal smoothed analysis of simplex
Bach and Huiberts proved an O(σ^(-1/2) d^(11/4) log(n)^(7/4)) smoothed pivot bound for a simplex method, with a matching lower bound in its dependence on the noise level σ.