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, 106 flashcards. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.
A jump-to index of every table row in this cheat sheet.
An interactive map of every table and concept in this topic.
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$ | ||
$z = 5x_1 + 4x_2$ | • Linear function to maximize or minimize • coefficients $c \in \mathbb{R}^n$ define contribution of each variable | ||
Convex polytope ${x : Ax \leq b,\ x \geq 0}$ | • Set of all $x$ satisfying all constraints • LP feasible region is always a convex polyhedron (possibly unbounded) | ||
$\min c^T x \equiv \max -c^T x$ | • Conversion: negate objective coefficients • all algorithms work on one form, result negated for the other | ||
$x_j \in \mathbb{R}$ → $x_j = x_j^+ - x_j^-,\ x_j^+, x_j^- \geq 0$ | • Variable without sign restriction • split into difference of two non-negative variables for standard-form solvers |