Linear Programming
Also known as: LP
Optimization of a linear objective subject to linear constraints.
Linear Programming is the optimization problem of maximizing or minimizing a linear objective function subject to linear equality and inequality constraints, with variables typically constrained to be non-negative. Standard form: maximize c^T x subject to Ax ≤ b, x ≥ 0. The discipline was substantially founded by George Dantzig's 1947 development of the Simplex Method, an algorithm that moves from vertex to vertex of the polyhedron defined by constraints, terminating at an optimal solution. Dantzig developed the method while working for the US Air Force on planning problems; the term 'programming' here meant scheduling/planning rather than computer programming. Independently and earlier (1939, with substantial development through 1940s), Soviet mathematician Leonid Kantorovich had developed similar techniques for production planning, for which he received the 1975 Nobel Memorial Prize in Economics (sharing with Tjalling Koopmans). Theoretical foundations include LP duality (every LP has a dual LP with deeply connected structure), the strong duality theorem, and the LP relaxation as foundation for discrete optimization. Subsequent algorithmic development includes Khachiyan's 1979 ellipsoid method (first polynomial-time LP algorithm), Karmarkar's 1984 interior-point method (practical polynomial-time alternative to Simplex), and modern primal-dual interior-point methods. LP is foundational to operations research, has substantial applications across economics, finance (portfolio optimization), logistics (transportation and assignment problems), engineering (resource allocation), and forms the foundation for integer programming, mixed-integer programming, and many discrete optimization formulations through LP relaxation.
Core components
- Linear objective function
- Linear equality and inequality constraints
- Non-negativity constraints (typical)
- Standard form, canonical form, slack variables
- Simplex method (Dantzig 1947, vertex-to-vertex movement)
- LP duality (primal-dual relationship, strong duality theorem)
- Sensitivity analysis and shadow prices
- Interior-point methods (Karmarkar 1984 and subsequent)
- Foundation for integer programming via LP relaxation
- Connection to game theory (LP duality and minimax)
- Substantial commercial solvers (Gurobi, CPLEX, COIN-OR CBC)
Primary use case
Foundation of operations research; resource allocation problems across industries; logistics, transportation, and assignment problems; production planning and scheduling; financial portfolio optimization; network flow problems; foundation for mixed-integer programming via LP relaxation; pedagogical foundation in operations research, applied mathematics, and quantitative business education; substantial commercial software ecosystem.
Common criticisms
- Real-world problems often have nonlinear features (economies of scale, integer indivisibilities, fixed costs) that LP can't directly model — requires extensions to nonlinear programming, integer programming, or mixed-integer programming
- LP relaxation gap for some discrete problems is large, limiting LP's usefulness for discrete optimization in those cases
- large-scale LPs (millions of variables and constraints) can challenge even modern solvers despite the theoretical polynomial-time complexity
- modeling skill — translating real problems into LP form — is the principal practical challenge
- degenerate LPs can cause Simplex method to cycle (resolved by anti-cycling rules but adds complexity)
- sensitivity analysis assumes infinitesimal changes that may not match practical decision-making
- LP optimal solutions can be brittle to small parameter changes
- commercial solvers' polynomial-time guarantees mask substantial constant-factor variation in practice.
Lineage
- Child of
- Optimization Theory
- Siblings
- Optimization Theory
- Derived from
- Optimization Theory