## Definition **Linear Programming (LP)** is the optimisation problem with a *linear* objective and *linear* constraints (equalities and inequalities). Polynomial-time solvable; the most efficient and widely-deployed mathematical programming framework. ## Standard Form $ \min_x \, c^\top x \quad \text{subject to} \quad A x \leq b, \quad x \geq 0 $ - $x \in \mathbb{R}^n$ — decision variables. - $c$ — cost vector. - $A, b$ — constraint matrix and bounds. Equality constraints can be added; minimisation/maximisation interchanged by sign flip. ## Why LP Is Special - **Convex.** Linear functions are convex; affine constraints define a convex polytope. - **Polynomial-time solvable.** Interior-point methods in $O(n^{3.5})$ worst case. - **Optimum at a vertex** of the feasibility polytope (when bounded). [[Simplex Method]] exploits this. ## Classic Problem Examples ### Diet Problem (Stigler, 1939) Minimise food cost subject to meeting nutritional requirements. Variables: amounts of each food. ### Transportation Problem Ship goods from sources to destinations at minimum cost, subject to supply and demand constraints. ### Production Planning Decide how much of each product to make, subject to resource limits and demand forecasts. ### Network Flow Maximise flow from source to sink across a network with edge capacities. ## Algorithms - **[[Simplex Method]]** (Dantzig, 1947). Walk along edges of the polytope. Exponential worst case but very fast in practice. - **Interior-point methods** (Karmarkar, 1984). Polynomial; competitive with Simplex on most large problems. - **Network simplex** for transportation / network flow problems. Modern solvers (CPLEX, Gurobi, GLPK, HiGHS, OR-Tools) routinely solve LPs with millions of variables and constraints in seconds. ## Why LP Underlies So Much - **Integer programming relaxation.** Drop integrality; solve LP; round or branch. See [[Integer Linear Programming]]. - **Combinatorial optimisation.** Many problems reduce to LP. - **Network flow algorithms.** Generalise LP structures. - **Game theory.** Zero-sum games solve as LPs. ## LP Duality Every LP has a dual: | Primal | Dual | |---|---| | min $c^\top x$ | max $b^\top y$ | | subject to $Ax \geq b$ | subject to $A^\top y \leq c$ | | $x \geq 0$ | $y \geq 0$ | **Strong duality** holds: if either has an optimum, both do and the optimal values are equal. The dual gives bounds, sensitivity analysis, and economic interpretation (shadow prices). See [[Duality]]. ## Limitations - Linearity is a strong assumption. Many real problems aren't linear (revenue often non-linear in production, etc.). - Doesn't natively model integer decisions — that's [[Integer Linear Programming]]. - Sensitive to constraint formulation; modelling skill matters. ## When to Use - **Resource allocation** problems with linear costs and constraints. - **Network flow** problems. - **As a relaxation** for combinatorial problems. - **First step** when modelling any new optimisation problem — check if linear suffices. ## Related - [[Simplex Method]] - [[Duality]] - [[Integer Linear Programming]] - [[Convex Optimization]]