= Gomory fractional cut
{c}
{title2=$\sum_j\{a_j\}x_j\geq\{b\}$}
For an all-integer dictionary row $x_B+\sum_j a_jx_j=b$ with nonnegative variables, this cut follows because $x_B+\sum_j\lfloor a_j\rfloor x_j$ is an integer and $\sum_j\{a_j\}x_j\geq0$. Consequently that integer is at most $\lfloor b\rfloor$. Negative coefficients use the usual <fractional part> $u-\lfloor u\rfloor$, so $\{-1/5\}=4/5$. Normalize a resulting inequality sensibly before introducing a new integer-valued <slack variable>.
Back to article page
