Chapter 29: Linear Programming: Formulations, Algorithms, and Duality

A linear program consists of decision variables, a linear objective function to maximize or minimize, and a set of linear inequality or equality constraints, compactly expressed in matrix form as minimizing cᵀx subject to Ax ≥ b and x ≥ 0, with a solution classified as feasible if it satisfies all constraints, optimal if it is feasible and achieves the best objective value, and the LP itself as bounded, unbounded, or infeasible depending on whether a finite optimum exists. Geometrically, constraints define half-spaces whose intersection forms a convex feasible region, and the optimal solution — when it exists — lies at a vertex of this region, an insight that motivates the simplex method, which moves along corner points of the feasible region and is highly efficient in practice despite an exponential worst case. The ellipsoid algorithm was the first theoretically polynomial-time LP solver, while interior-point methods offer polynomial-time performance with practical efficiency on large sparse systems. The chapter demonstrates LP's expressive power by formulating classic problems within it: shortest paths arise from maximizing distances subject to triangle inequality constraints, maximum flow from maximizing net source outflow subject to capacity and conservation, and multicommodity flow from ensuring multiple flows share edge capacities feasibly. Duality theory reveals that every LP has a corresponding dual — swapping variables and constraints and flipping the optimization direction — with weak duality bounding the primal by the dual and strong duality guaranteeing equal optimal values when both are feasible, linked at optimality through complementary slackness and grounded in Farkas's Lemma. The chapter closes by contrasting LP with integer linear programming, where restricting variables to integers makes the problem NP-hard and requires techniques like branch-and-bound and cutting planes.