Linear Programming (LP) is the problem of maximising or minimising a linear objective function subject to a finite set of linear equality and inequality constraints. The feasible region is a convex polyhedron, and the optimal solution — if it exists — lies at a vertex of that polyhedron. LP is the most widely solved class of optimisation problem in practice: every mixed-integer programme relaxes to an LP at each node of the branch-and-bound tree, every column-generation master is an LP, and every Benders decomposition subproblem is an LP.
Three algorithm families dominate LP solving. The simplex method (Dantzig, 1947) walks along vertices of the polyhedron, pivoting to adjacent vertices with improving objective values; it is efficient in practice despite worst-case exponential complexity and supports warm-starting from a prior basis. Interior-point methods (IPMs) (Karmarkar, 1984) traverse the interior of the feasible region along a central path toward optimality; they run in polynomial time and dominate on large, dense instances. First-order methods such as the Primal-Dual Hybrid Gradient (PDHG) algorithm solve the LP as a saddle-point problem using matrix-vector multiplications without factoring the constraint matrix; they scale favourably on very large sparse instances where factorisation is the bottleneck.
The problem: A factory produces two products using three machines. Each product requires a known amount of time on each machine, and each machine has a limited number of hours available per week. Each product earns a known profit per unit. The factory wants to maximise weekly profit.
LP formulation: Let x₁ and x₂ be the number of units of each product. The objective is max c₁x₁ + c₂x₂ (profit). The constraints are a₁₁x₁ + a₁₂x₂ ≤ b₁ (machine 1 hours), and similar constraints for machines 2 and 3, plus x₁, x₂ ≥ 0.
Result: The simplex method finds the optimal production mix at a vertex of the feasible polygon in two or three pivots. The dual variables (shadow prices) on the machine-hour constraints tell the factory how much one additional hour on each machine would be worth — directly informing capacity investment decisions.
“LP is too simple for real problems.” In practice, LP relaxations are the computational engine inside every MIP solver, every column-generation loop, and every Benders decomposition. Improving LP solve time by 2× can cut end-to-end MIP solve time by 10× because the LP relaxation is solved thousands of times during branch-and-bound. LP is not the toy version of optimisation — it is the load-bearing component.
“Algorithm choice doesn’t matter — the solver picks for me.” Solver defaults are tuned for average-case performance across benchmark suites. For a specific application class at production scale, the asymptotic scaling of simplex, IPM, and PDHG can diverge by orders of magnitude. Benchmarking algorithm choice on your problem class is a zero-cost lever that practitioners routinely leave on the table.
“LP means the problem is easy.” LP is solvable in polynomial time, but that does not mean every LP instance is fast. Power-systems dispatch LPs with millions of variables and network-flow structure can take hours with the wrong algorithm. Degeneracy (many vertices with the same objective value) can cause the simplex method to stall. Numerical conditioning can cause IPMs to lose precision. LP is tractable in theory; making it fast in practice requires understanding problem structure.
Linear Programming optimises a linear objective over a polyhedron defined by linear constraints; it is the foundational building block of MIP, column generation, and Benders decomposition, and the algorithm choice between simplex, interior-point, and first-order methods matters more than most practitioners realise.