What Is Linear Programming?

Linear programming is a mathematical optimization technique for finding the maximum or minimum value of a linear objective function subject to a set of linear equality and inequality constraints. The variables must satisfy all constraints simultaneously, and the feasible region defined by those constraints forms a convex polyhedron in the decision variable space. Because both the objective and the constraints are linear, the optimal solution always occurs at a vertex of this polyhedron (or on an edge between two vertices when multiple optima exist). Linear programming forms the foundation of operations research and is one of the most widely applied optimization methodologies in engineering, economics, and logistics.

The field was formalized by George Dantzig, who developed the simplex algorithm in 1947 while working on planning problems for the U.S. Air Force. Dantzig's work provided a systematic way to search the vertices of the feasible polyhedron efficiently and was recognized as one of the most significant algorithmic contributions of the twentieth century. Linear programming draws on linear algebra, convex geometry, and the duality theory that connects every maximization problem to a corresponding minimization problem.

Mathematical Formulation

A linear program in standard form minimizes the dot product of a cost vector c with a decision vector x, subject to the constraint that a matrix A times x equals a vector b and all components of x are nonneg­ative. The feasible set of all vectors satisfying the constraints is a convex polytope, and the level sets of the objective function are parallel hyperplanes. The duality theorem states that every primal linear program has a dual whose optimal objective value equals the primal's, a result with deep economic interpretations: the dual variables are shadow prices that represent the marginal value of each constraint. Strong duality holds whenever both the primal and dual are feasible, and complementary slackness conditions characterize the relationship between primal and dual optimal solutions. The Cornell Optimization Wiki entry on the simplex algorithm gives a clear treatment of these geometric and algebraic foundations.

The Simplex Method

The simplex method, published by Dantzig in 1947 and analyzed in detail in Computing in Science and Engineering, traverses the vertices of the feasible polyhedron by repeatedly moving to an adjacent vertex that improves the objective. At each iteration, a pivot operation selects the entering variable that will reduce the objective and the departing variable that maintains feasibility, then updates the basis. The number of iterations is typically proportional to the number of constraints, making the simplex method very fast in practice, though Klee and Minty constructed pathological examples requiring exponential iterations. Revised simplex methods update only the basis inverse, reducing computation per iteration for large sparse problems. Branch-and-bound methods, which solve sequences of linear relaxations using the simplex algorithm, extend the approach to mixed-integer linear programs.

Interior-Point Methods

Interior-point methods, developed by Karmarkar in 1984 and extended through the 1990s, traverse the interior of the feasible polytope along a central path rather than moving along edges. They are polynomial in the problem size, with worst-case complexity scaling as O(n^{3.5} L) operations. For large-scale problems with hundreds of thousands of variables, interior-point solvers such as IPOPT, Gurobi, and CPLEX often outperform the simplex method in wall-clock time. The primal-dual path-following algorithm, widely used in modern solvers, simultaneously updates primal and dual variables to maintain near-central paths until convergence. The Gurobi technical blog on linear programming with the simplex method provides a practical comparison of these algorithmic approaches.

Applications

Linear programming has applications across a range of fields, including:

• Supply chain and logistics optimization for transportation and inventory
• Production planning and resource allocation in manufacturing
• Portfolio optimization and financial risk management
• Network flow problems including shortest paths and maximum flow
• Microeconomics and competitive equilibrium analysis