Linear Programming (LP)
Linear Programming (LP) is one of the most fundamental and widely used problem classes in operations research and optimization. It provides a mathematical framework for modeling and solving problems where both the objective function and the constraints are linear. Despite its apparent simplicity, linear programming has had a profound impact across industries, powering decision-making in logistics, finance, energy, telecommunications, and more.
What is Linear Programming?
More formally, linear programming is a mathematical technique for optimizing a linear objective function, subject to a collection of linear equality and inequality constraints. The feasible region defined by these constraints is a convex polytope: the intersection of finitely many half-spaces, each specified by a linear inequality. The objective function itself is a real-valued affine (linear) function defined on this polytope. A general LP takes the form:
\text{maximize } c^T x \quad \text{subject to } Ax \leq b, \; x \geq 0Where:
- x represents the decision variables,
- c^T x is the objective function (linear in x),
- Ax \leq b represents a set of linear constraints.
Solving Linear Programs
A linear programming algorithm seeks a point in the polytope where the objective function reaches its maximum or minimum value. Thanks to the polyhedral structure of the feasible region, at least one optimal solution always occurs at a vertex (corner point) of the polytope—a property that underlies the efficiency of algorithms like the Simplex method, which moves from vertex to vertex until optimality is achieved.
Several powerful approaches exist for solving LPs efficiently, even at large scale. As mentioned above, the classic Simplex algorithm leverages the polyhedral structure by navigating along the vertices, while Interior-Point methods approach optimality from within the feasible region and scale particularly well for very large problems. Modern solvers often combine these techniques to maximize both speed and robustness.
Because LP models can be solved quickly and reliably, they are often used as relaxations for more complex problems. For example, in solving a MILP, a solver repeatedly solves LP relaxations inside a Branch-and-Bound framework. LP is also central to decomposition approaches such as Dantzig–Wolfe decomposition and Benders decomposition, as well as in heuristic methods like LP-based rounding.
Extensions and related problem classes
Linear programming often serves as the gateway problem to more complex optimization classes:
- Mixed-Integer Linear Programming (MILP): Extends LP by introducing integer decision variables, enabling discrete choices and combinatorial structure.
- Quadratic Programming (QP): Generalizes LP by allowing quadratic objectives while keeping linear constraints.
- Convex Programming: A broader class where the feasible region and objective remain convex, of which LP is a special case.
Further reading and references
Dantzig, G. B. (1947). Maximization of a Linear Function of Variables Subject to Linear Inequalities. In Activity Analysis of Production and Allocation (T. Koopmans, ed.), Wiley.
The original paper describing the Simplex algorithm and establishing linear programming as a formal field.
Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press.
The classic text by the creator of the Simplex method. Establishes the theoretical and computational foundations of linear programming, including duality and decomposition methods.
Vanderbei, R. J. (2014). Linear Programming: Foundations and Extensions (4th ed.). Springer.
A comprehensive modern reference linking LP theory to computational methods like network flow, interior-point algorithms, and convex optimization.