Linear Programming: Optimizing with Linear Constraints
Introduction
Linear programming (LP) solves optimization problems where the objective function and all constraints are linear. Despite the restriction to linearity, LP problems arise in astonishing variety: manufacturing companies minimizing production costs, airlines maximizing revenue from ticket sales, investment firms optimizing portfolio allocations, and logistics companies minimizing shipping distances.
The power of linear programming comes from three features. First, linearity captures a wide range of practical resource allocation problems. Second, the mathematical structure of linear programs enables efficient solution algorithms that handle millions of variables. Third, sensitivity analysis reveals how the optimal solution changes with problem data, providing insight beyond the simple optimal value.
Problem Formulation
Every linear program has three components: decision variables, a linear objective function, and linear constraints. The standard form minimizes cᵀx subject to Ax = b, x ≥ 0. The equality constraints come from adding slack variables to inequality constraints. Nonnegativity constraints reflect that most real quantities cannot be negative.
Converting Problems to Standard Form
Maximization becomes minimization by negating the objective. Inequality constraints aᵀx ≤ b become equalities by adding slack variables s ≥ 0: aᵀx + s = b. Unrestricted variables are split into positive and negative parts: x = x⁺ − x⁻, where x⁺, x⁻ ≥ 0.
The matrix A has m rows (constraints) and n columns (variables). Typically n > m, giving more variables than equations. The excess degrees of freedom allow optimization. Basic feasible solutions set n−m variables to zero and solve for the remaining m variables, corresponding to vertices of the feasible polytope.
Geometric Interpretation
The feasible region of an LP is a convex polytope — the intersection of half-spaces defined by the linear constraints. The objective function is linear, so its level sets are parallel hyperplanes. The optimal solution occurs at a vertex of the polytope, where the objective hyperplane is as low as possible while still intersecting the feasible region.
This geometric view explains why LPs can be solved efficiently: the search for the optimum reduces to checking vertices rather than exploring the entire feasible region. The number of vertices can be large, but algorithms that move intelligently among them reach the optimum in polynomial time.
Geometry of Linear Programs
The feasible region of an LP is a convex polytope defined by the intersection of half-spaces. Each constraint corresponds to a half-space boundary (a hyperplane). The feasible region is the set of points satisfying all constraints simultaneously. The objective function is a linear functional whose level sets are parallel hyperplanes.
The optimal solution occurs at a vertex of the polytope where the objective function level set just touches the feasible region. If multiple vertices achieve the same optimal value, the entire face connecting them is optimal. This geometric understanding justifies searching vertices rather than interior points, leading directly to the simplex method.
The Simplex Method
The simplex method, developed by George Dantzig in 1947, moves from vertex to vertex along edges of the feasible polytope, always improving the objective. It begins at a basic feasible solution and at each step selects an entering variable (whose increase improves the objective) and a leaving variable (determined by the tightest constraint).
Phase I and Phase II
Phase I finds an initial basic feasible solution by solving an auxiliary LP. Phase II optimizes the actual objective starting from this feasible solution. For problems with obvious feasible solutions — all constraints of the form Ax ≤ b with b ≥ 0 — Phase I can be skipped by using slack variables as the initial basis.
The algorithm terminates when no entering variable can improve the objective — the current vertex is optimal. In rare cases of degeneracy (more than n constraints active at a vertex), the algorithm may cycle. Bland’s rule prevents cycling by specifying a deterministic variable selection order.
Interior Point Methods
Interior point methods approach the optimal solution through the interior of the feasible region rather than along its edges. The central path is a curve through the interior parameterized by a barrier parameter that controls how closely constraints are approached. As the barrier parameter goes to zero, the central path converges to the optimal vertex.
Karmarkar’s 1984 interior point algorithm sparked a revolution in optimization by proving polynomial-time complexity for linear programming, unlike the exponential worst-case of simplex. Modern interior point methods use Newton steps to follow the central path, solving large sparse LPs with thousands of constraints in practical time.
Computational Performance
The simplex method has exponential worst-case complexity (Klee-Minty cubes), but in practice it solves most problems in O(m²n) operations. The number of iterations grows roughly linearly with m, far better than the exponential worst case suggests. This remarkable practical performance has made the simplex method the standard LP algorithm for decades.
Duality Theory
Every linear program has a companion dual problem. The dual of a minimization LP is a maximization LP, with variables corresponding to constraints in the primal and constraints corresponding to variables in the primal. The dual variables represent shadow prices — the marginal value of relaxing each constraint.
Weak and Strong Duality
Weak duality states that any feasible dual objective value is a lower bound on the optimal primal objective (for minimization primal). Strong duality states that at optimality, the primal and dual objectives are equal — provided both are feasible. This equality provides a certificate of optimality: a feasible primal-dual pair with equal objectives is optimal.
Complementary slackness refines the relationship: at optimality, for each primal constraint, either the constraint is tight (slack variable zero) or the corresponding dual variable is zero. These conditions provide another way to verify optimality and are the foundation of primal-dual algorithms.
Economic Interpretation
Dual variables (shadow prices) measure the rate of change of the optimal objective with respect to changes in constraint right-hand sides. If a manufacturing constraint has shadow price $5, relaxing that constraint by one unit increases profit by $5. Resources with positive shadow prices are bottlenecks. Resources with zero shadow price are abundant.
Sensitivity Analysis
The optimal solution depends on the problem data — objective coefficients, constraint coefficients, and right-hand sides. Sensitivity analysis determines how the optimal solution changes when this data changes, without resolving the entire problem.
Degeneracy and Cycling
A basic feasible solution is degenerate if some basic variable equals zero, meaning more than n constraints are active at that vertex. Degeneracy can cause the simplex method to stall — moving to adjacent vertices without improving the objective. In rare cases, degeneracy leads to cycling, where the algorithm revisits the same vertices repeatedly.
Bland’s rule prevents cycling by specifying a deterministic variable selection order: among all eligible entering variables, choose the one with the smallest index; among all eligible leaving variables, choose the one with the smallest index. In practice, cycling is extremely rare, and most implementations use simpler pivot rules with perturbation techniques to handle degeneracy.
Changes in Objective Coefficients
The reduced cost of a nonbasic variable measures how much the objective coefficient must change before that variable becomes profitable to include. If a nonbasic variable has reduced cost greater than the available profit margin, its coefficient would need to increase beyond the reduced cost to make it enter the basis.
Objective coefficient ranges specify the interval over which the current basis remains optimal. Within this range, the optimal vertex stays the same; the objective value changes linearly with the coefficient. Outside this range, the basis changes.
Changes in Right-Hand Sides
The shadow price applies only over a specific range of right-hand side values. Beyond this range, the basis changes and the shadow price may differ. The allowable increase and decrease define this range, computed from the optimal tableau’s inverse.
Integer Programming
Many real problems require integer decisions: number of employees, number of trucks, yes/no decisions. Integer linear programming forces some or all variables to be integer. Branch and bound solves integer programs by recursively dividing the feasible region into subproblems and computing LP relaxations as bounds.
Branch and Cut
Cutting planes add constraints that cut off fractional solutions without removing integer feasible points. Branch and cut combines branch and bound with cutting planes, adding cuts at each node of the search tree. This approach solves many practical integer programs efficiently.
Valid inequalities are constraints satisfied by all integer feasible points but violated by the current fractional solution. Gomory cuts are derived from the simplex tableau. Cover cuts apply to knapsack constraints. Lift-and-project cuts generalize to arbitrary 0-1 programs. The art of integer programming lies in generating effective cuts that tighten the relaxation without excessive computational cost.
Cutting planes add constraints that cut off fractional solutions without removing integer feasible points. Branch and cut combines branch and bound with cutting planes, adding cuts at each node of the search tree. This approach solves many practical integer programs efficiently.
Integer programming is generally NP-hard — no polynomial-time algorithm exists unless P = NP. However, real-world instances with thousands of variables are routinely solved using commercial solvers like CPLEX and Gurobi.
Applications
Linear programming drives modern logistics. FedEx and UPS optimize package routing with LP models containing millions of constraints. Airlines solve crew scheduling LPs to assign pilots and flight attendants to flights while satisfying complex work rules and minimizing costs.
Portfolio optimization uses LP to allocate investments subject to diversification constraints and return targets. Manufacturing companies use LP to plan production, inventory, and distribution across supply chains. Energy companies use LP to schedule power generation and transmission.
Network flow problems are a special class of LPs with unimodular constraint matrices, guaranteeing integer solutions when the right-hand sides are integer. The transportation problem ships goods from suppliers to customers at minimum cost. The assignment problem matches workers to jobs optimally. The max-flow problem finds the maximum amount that can flow through a network from source to sink subject to capacity constraints. These problems are solved by specialized algorithms orders of magnitude faster than general LP solvers.
What makes a problem linear? A linear program has a linear objective function and linear constraints. Linearity means the objective and constraints are sums of variables multiplied by constants, without any product of variables, powers, or nonlinear functions.
What is a shadow price? A shadow price (dual variable) measures how much the optimal objective changes per unit increase in a constraint’s right-hand side. It represents the marginal value of relaxing that constraint.
How does the simplex method work? The simplex method starts at a feasible vertex and moves along edges to neighboring vertices, always improving the objective, until reaching the optimal vertex.
When do I need integer programming? Integer programming is needed when decision variables represent discrete choices — number of items to produce, whether to build a facility, which routes to use. The solutions must be integers, not fractions.
Optimization Theory — Computational Mathematics — Mathematical Modeling