= Linear programming optimality certificate
{title2=$c^Tx=y^Tb$}
For the <linear program> maximizing $c^Tx$ with $Ax\le b$, $x\ge0$, a vector $y\ge0$ with $A^Ty\ge c$ proves $c^Tx\le y^Tb$ for every feasible $x$. If a feasible $x$ attains that bound, it is optimal. This is <weak duality> written as a directly checkable certificate; adding nonnegative multiples of constraints suffices to verify it. The equivalent reversed-inequality certificate applies to a minimization program.
Back to article page
