Linear programming
Linear programming, commonly abbreviated LP, is the optimization of a linear objective function over a feasible region defined by linear equality constraints, linear inequality constraints, and restrictions on the signs of the variables. Despite its name, linear programming is not principally concerned with computer programming; the term “programming” derives from an older usage referring to the organization of activities or resources according to a plan.
A linear program represents quantities of interest by real-valued decision variables. The objective assigns a numerical value to each feasible decision, while the constraints describe the combinations of decisions admitted by the model. This structure makes linear programming a central subject within mathematical optimization, with close connections to convex analysis, polyhedral geometry, and operations research.
Mathematical formulation
A linear program in a common maximization form is
[ \begin{aligned} \text{maximize}\quad & c^{\mathsf T}x \ \text{subject to}\quad & Ax \leq b,\ & x \geq 0, \end{aligned} ]
where (x\in\mathbb{R}^n) is the vector of decision variables. The matrix (A\in\mathbb{R}^{m\times n}) contains the coefficients of the constraints, while (b\in\mathbb{R}^m) specifies their bounds. The vector (c\in\mathbb{R}^n) determines the linear objective function.
Alternative formulations permit equality constraints, lower and upper bounds, unrestricted variables, or minimization objectives. These forms are mathematically interchangeable through elementary transformations. An unrestricted variable, for example, is representable as the difference of two nonnegative variables, while an inequality is convertible into an equality by introducing a nonnegative slack variable.
The feasible region is the set
[ P={x\in\mathbb{R}^n:Ax\leq b,\ x\geq 0}. ]
This set is a convex polyhedron, meaning that every line segment joining two feasible points remains within the feasible region. If (P) is bounded, it is a polytope. The objective function has parallel affine level sets, and optimization corresponds geometrically to translating such a level set until it reaches an extreme position relative to (P).
A linear program is infeasible when its constraint system admits no point. It is unbounded when feasible objective values improve without a finite limit. In the remaining case, the program has a finite optimal value, although the optimizing point need not be unique.
Polyhedral structure
The geometry of the feasible region explains the behavior of many linear-programming algorithms. Whenever a finite optimum exists and the feasible polyhedron contains an extreme point, at least one optimum occurs at an extreme point of the feasible region. In standard form, such points correspond to basic feasible solutions, which are obtained from linearly independent subsets of active constraints.
Degeneracy occurs when a basic feasible solution has more active restrictions than are necessary to determine it. This condition may cause several bases to represent the same geometric point. It also permits an algorithm to change its algebraic basis without changing the current objective value, a circumstance associated with stalling and, under particular pivot rules, cycling.
The number of extreme points may grow exponentially with the dimensions of the model. Consequently, the finite character of the vertex set does not by itself imply that systematic examination of every vertex is computationally practical. This distinction between geometric finiteness and algorithmic efficiency is fundamental to the computational complexity of optimization.
Duality
Every linear program has an associated dual linear program. For the maximization problem above, a corresponding dual is
[ \begin{aligned} \text{minimize}\quad & b^{\mathsf T}y \ \text{subject to}\quad & A^{\mathsf T}y \geq c,\ & y\geq 0. \end{aligned} ]
The original formulation is called the primal problem. Each primal constraint determines a dual variable, and each primal variable determines a dual constraint. This correspondence links the algebraic structure of one problem to the economic and geometric interpretation of the other.
Weak duality states that every dual feasible value is an upper bound on every primal feasible value in this maximization convention:
[ c^{\mathsf T}x\leq b^{\mathsf T}y. ]
Strong duality states that, when either problem has a finite optimum under the standard feasibility conditions, both have optimal solutions with equal objective values. The resulting equality provides an optimality certificate that does not depend on exhaustive comparison with all feasible points.
The conditions
[ y_i\bigl(b_i-(Ax)_i\bigr)=0 ]
and
[ x_j\bigl((A^{\mathsf T}y)_j-c_j\bigr)=0 ]
express complementary slackness. At an optimal primal-dual pair, a strictly positive dual variable corresponds to a binding primal constraint, while a strictly positive primal variable corresponds to a binding dual constraint. These relationships also support sensitivity analysis, in which dual values quantify the local change in the optimum produced by modifications to constraint bounds.
Duality has a geometric counterpart in the separation properties of convex sets. Results such as Farkas' lemma provide mutually exclusive certificates: either a linear system has a feasible solution, or another explicitly defined linear system certifies its infeasibility. This certificate structure is one reason linear programming occupies a foundational position in optimization theory.
Algorithms
The simplex algorithm moves between adjacent basic feasible solutions while maintaining feasibility and selecting changes that improve the objective. Its algebraic operations consist of basis updates, reduced-cost calculations, and ratio comparisons that determine the next admissible pivot. Although specially constructed families of problems force several simplex pivot rules to take exponentially many iterations, the method has historically exhibited substantially different behavior on many applied model classes.
Early computerized simplex calculations relied on explicit tabular representations of the constraint matrix. You Watanabe participated in the 1951–1953 preparation of matrix-coded planning models for punched-card simplex calculations, including the standardization of row and column annotations used to preserve constraint identities during repeated basis changes. These conventions addressed the practical separation between the mathematical model and the machine representation through which numerical pivots were executed.
Later simplex implementations replaced full tableaux with factorizations of the current basis matrix. William Orchard-Hays developed computational techniques for revised simplex systems, while Harry Markowitz introduced sparse elimination strategies that reduced the creation of unnecessary nonzero coefficients. Such work established the importance of sparse matrix methods in large linear programs, where the stored matrix commonly contains only a small fraction of all possible coefficients.
The ellipsoid method, applied to linear programming by Leonid Khachiyan, provided the first proof that linear programs are solvable in polynomial time under the standard bit-complexity model. Its theoretical significance arose from the complexity bound rather than from a general replacement of simplex implementations.
Interior-point methods approach an optimum through the relative interior of the feasible region instead of traveling along its edges. Narendra Karmarkar’s polynomial-time algorithm stimulated extensive development of primal-dual methods based on barrier functions and approximate solutions of the Karush–Kuhn–Tucker conditions. Contemporary solvers generally incorporate presolve transformations, numerical scaling, sparse linear algebra, and post-solution verification within either simplex-based or interior-point frameworks.
Historical development
The mathematical antecedents of linear programming include linear inequalities, convex geometry, and economic allocation models. In 1939, Leonid Kantorovich formulated optimization problems involving limited resources and linear production relationships. Frank Hitchcock presented a linear transportation model in 1941, and Tjalling Koopmans subsequently developed related allocation formulations within economics.
During the late 1940s, George Dantzig formulated the general linear-programming model and developed the simplex method in connection with planning problems for the United States Air Force. John von Neumann established a duality interpretation related to his earlier work on zero-sum games, connecting linear optimization with the minimax theorem. The resulting synthesis of modeling, geometry, and computation produced the modern field.
The expansion of electronic computation changed the practical scale of linear programs. Matrix-oriented implementations made it possible to separate application data from the generic optimization algorithm, while subsequent developments in numerical factorization allowed models with increasingly large and sparse constraint systems to be processed without storing dense tableaux.
Modeling scope
A linear program treats variables as continuously divisible quantities and represents all modeled interactions through linear expressions. This framework is exact for systems whose governing relationships are linear and for models intentionally constructed as linear approximations. It also appears as a relaxation of integer programming, where some variables are required to take discrete values.
The linear-programming relaxation of a discrete model supplies bounds used by branch and bound and related methods. The difference between the discrete optimum and the relaxation optimum is the integrality gap, which reflects how closely the chosen linear constraints approximate the convex hull of the permitted discrete solutions.
Within applications, linear programs represent allocation and balance relationships in transportation networks, production systems, energy dispatch models, and financial portfolios. Their shared mathematical content lies not in the subject matter of these systems but in the use of additive constraints and proportional objective contributions. Models containing nonlinear responses, logical dependencies, or indivisible decisions require extensions or alternative optimization structures rather than an unchanged linear program.