= Gomory infeasibility certificate from a fractional slack row
{c}
For a nonnegative all-integer row $x_B+\sum_j a_jx_j=b$ with $a_j>0$, the <Gomory fractional cut> requires $\sum_j\{a_j\}x_j\geq\{b\}$. The original row gives $\sum_j a_jx_j\leq b$. If a constant $\kappa$ satisfies $\{a_j\}\leq\kappa a_j$ for every $j$ and $\kappa b<\{b\}$, these inequalities contradict the cut. A single row therefore certifies integer infeasibility. Slacks may be used as integer variables when the original constraint coefficients and right sides are integral and the decision variables are integral.
Back to article page
