Linear Programming
Motivation
A staggering number of optimization problems in operations research, machine learning, and economics reduce to: minimize a linear cost function subject to a set of linear inequality constraints. This is linear programming (LP), and it is one of the most important computational tools of the twentieth century. Unlike its integer cousin, LP is solvable in polynomial time — a result that turned LP into a routine subroutine of larger algorithms (column generation, branch and bound, LP relaxation for NP-hard problems) (Dantzig 1963; Boyd and Vandenberghe 2004; Kleinberg and Tardos 2005).
Beyond direct applications (resource allocation, network flow, transportation, portfolio selection), LP is the foundation for understanding convex optimization more broadly: most convex optimization algorithms generalize LP techniques to nonlinear costs and constraints.
Standard form
A linear program is \[ \begin{aligned} \text{minimize} \quad & c^\top x \\ \text{subject to} \quad & A x \le b \\ & x \ge 0, \end{aligned} \] with \(c \in \mathbb{R}^n\), \(A \in \mathbb{R}^{m \times n}\), \(b \in \mathbb{R}^m\). The variables \(x \in \mathbb{R}^n\) are continuous (no integrality constraint — that would make it an integer LP).
Equivalent forms exist: minimize vs. maximize (negate \(c\)), \(\le\) vs. \(\ge\) (negate the row), equality vs. inequality (use slack variables). All are polynomial-time inter-convertible.
Geometry
The feasible set \(\{x : A x \le b, x \ge 0\}\) is the intersection of finitely many halfspaces — a polyhedron. If the polyhedron is bounded, it is a polytope.
Key geometric facts:
- The feasible region is convex: any line segment between two feasible points is feasible.
- The objective \(c^\top x\) is linear (in particular, both convex and concave).
- The optimum, if finite, is achieved at a vertex of the polyhedron — a point where \(n\) linearly independent constraints are tight. (If multiple vertices tie, an entire face is optimal.)
Because the optimum is at a vertex, LP is in principle a finite combinatorial problem — try every vertex — but the number of vertices can be exponential in \(n\).
Example: a 2-D LP
Consider the 2-variable LP in maximization form:
\[ \begin{aligned} \text{maximize} \quad & 3x_1 + 2x_2 \\ \text{subject to} \quad & 2x_1 + 2x_2 \le 9, \\ & x_1 \le 3, \\ & x_2 \le 3, \\ & x_1, x_2 \ge 0. \end{aligned} \]
The shaded pentagon below is the feasible polyhedron — the intersection of five halfspaces. The three non-negativity conditions fix the lower-left boundary; the three labeled constraints (dashed gray lines) define the remaining edges.
The dashed red line is the level curve \(3x_1 + 2x_2 = 12\), tangent to the feasible region at the optimal vertex. The arrow \(\nabla c = (3,\,2)\) points in the direction of increasing objective; moving further that way exits the polytope. Evaluating the objective at each vertex:
| Vertex | \((x_1,\,x_2)\) | \(3x_1 + 2x_2\) |
|---|---|---|
| \(A\) | \((0,\,0)\) | \(0\) |
| \(B\) | \((3,\,0)\) | \(9\) |
| \(C\) | \((3,\,\tfrac{3}{2})\) | \(\mathbf{12}\) |
| \(D\) | \((\tfrac{3}{2},\,3)\) | \(\tfrac{21}{2}\) |
| \(E\) | \((0,\,3)\) | \(6\) |
The optimum is \(C = (3,\,\tfrac{3}{2})\), the vertex where both \(x_1 = 3\) and \(2x_1 + 2x_2 = 9\) are tight — two linearly independent active constraints for two variables, exactly the vertex characterization above.
Outcomes
A linear program has exactly one of three outcomes:
- Infeasible: the feasible polyhedron is empty.
- Unbounded: feasible, but the objective can be driven to \(-\infty\) along some feasible ray.
- Optimal: a finite optimum is achieved (at some vertex, by the geometric fact above).
Example: the three outcomes
Each panel below shows a 2-D LP with \(x_1, x_2 \ge 0\). Axes run from \(0\) to \(4\).
halfspaces do not intersect.
is open; \(\nabla c\) drives cost to \(-\infty\).
reached at vertex \(C=(3,1)\).
Solving LPs
Three families of algorithms cover virtually all practical LP solvers (more detail):
- Simplex method (Dantzig 1963): walks vertex-to-vertex along edges of the polyhedron, always improving the objective. Worst-case exponential, but extraordinarily fast in practice.
- Ellipsoid method (Khachiyan 1979): the first proof that LP is in P. Theoretically important, slow in practice.
- Interior-point methods (Karmarkar 1984): traverse the interior of the feasible region following a polynomial-time central path. Fast in both theory and practice.
LP was first proven to be solvable in polynomial time by Khachiyan in 1979 via the ellipsoid method, and the result was made practical by Karmarkar in 1984 with interior-point methods.
Modelling examples
Diet problem. Choose quantities \(x_i\) of foods to minimize cost \(\sum c_i x_i\) subject to nutritional requirements \(\sum a_{ji} x_i \ge r_j\) and \(x_i \ge 0\).
Maximum flow. Send as much flow as possible from source to sink in a network with edge capacities, subject to flow conservation. The LP has one variable per edge.
Transportation. Ship goods from sources to destinations to minimize cost, subject to supply and demand constraints.
Linear regression with \(\ell_1\) loss / linear support vector machines (with hinge loss): both have natural LP formulations with auxiliary variables.
Duality
Every LP has a dual LP with intimately connected structure (detail). Weak and strong duality theorems link the two and underpin both algorithm design (interior-point methods exploit primal-dual symmetry) and economic interpretation (dual variables are shadow prices on the primal constraints). Zero-sum games and the minimax theorem are a celebrated special case.
What LP cannot do
LP is restricted to linear costs and constraints. Two important problem classes push LP in opposite directions — one relaxing linearity, one restricting variables to integers:
- Convex programming: convex (not just linear) objective, convex feasible region. Still polynomial-time solvable; includes quadratic programming, semidefinite programming, geometric programming.
- Integer linear programming: same form as LP but with integer variables. NP-hard. Solved in practice by branch and cut using LP as a relaxation.
The boundary “convex = easy, non-convex = hard” is a central organising principle of optimization theory; LP is the simplest interesting point inside the easy region.