Linear Programming (LP) is a mathematical optimization technique for maximizing or minimizing a linear objective function subject to linear constraints. The simplex method, introduced by George Dantzig in 1947, remains the dominant algorithm for solving LP problems in practice despite its worst-case exponential complexity, because it performs very efficiently on real-world instances. This cheat sheet covers LP formulation from first principles through advanced topics including duality theory, integer programming, interior-point methods, network flows, and practical solver usage.
What This Cheat Sheet Covers
This topic spans 16 focused tables and 129 indexed concepts. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.
LP Standard Form and Canonical Form
| Concept | Example | Description |
|---|---|---|
\max c^T x s.t. Ax \leq b,\ x \geq 0 | • Canonical max LP: objective is linear, all constraints are \leq inequalities, all variables non-negative• most solvers accept this as input | |
\max c^T x s.t. Ax = b,\ x \geq 0 | • Equality form used internally by simplex • obtained by adding slack variables • also called augmented or slack form | |
x_1 + x_2 + s_1 = 4,\ s_1 \geq 0 | • Non-negative variable added to convert \leq inequality to equality• s_i = b_i - a_i^T x measures unused capacity | |
x_1 + x_2 - e_1 = 2,\ e_1 \geq 0 | • Non-negative variable subtracted to convert \geq inequality to equality• e_i = a_i^T x - b_i |