LP Duality

Combine the constraints to bound the primal; the tightest such bound is the dual b^ y, and it meets the optimum.

The idea

Every linear program comes paired with a second one, its dual, and each of the pair bounds the other.

Write the primal as $\max\ c^{\top} x$ subject to $A x \le b$, $x \ge 0$. Its dual is

$\min\ b^{\top} y \quad \text{subject to} \quad A^{\top} y \ge c, \ y \ge 0.$

The right-hand side $b$ and the objective $c$ trade places, the inequalities flip direction, and $A$ is transposed.

Theorem (LP duality).

Let $x$ be feasible for the primal and $y$ feasible for the dual. Then (weak duality) $c^{\top} x \le b^{\top} y$. If moreover the primal is feasible and bounded, then (strong duality) both problems have optimal solutions and their optimal values coincide, $c^{\top} x^{} = b^{\top} y^{}$.

The dual is built from the primal's own constraints. It carries one variable $y_i \ge 0$ per primal constraint, and a dual-feasible $y$ is a certificate: it proves that no feasible point scores higher than $b^{\top} y$, without the primal being solved. The dual asks for the smallest such bound, and strong duality says the smallest bound is exact.

Ways to work on it

• Walkthrough. Design an upper bound by combining constraints, then discover that the best bound is the dual LP.
• Practice. Compute a dual objective (the certified bound) and state which value it bounds.
• Hardest. Build a dual constraint, then apply the optimality certificate.

Not sure where to start? Take the ten-question placement test.