# Gomory cut

This is an early cutting plane for an integer program. Consider $LaTeX: \{ (x, s) : x \in \mathbb{Z}^n, \; s \in \mathbb{R}^m, Ax + s = b, x \ge 0, s \ge 0 \}$, where $LaTeX: A$ and $LaTeX: b$ have integer values. For any $LaTeX: y \in \mathbb{R}^m$, let $LaTeX: a = A^T y - \lfloor A^T y \rfloor$ and $LaTeX: a_0 = y^T b - \lfloor y^T b \rfloor$ (i.e., $LaTeX: a$ is the fractional part of the linear combination of the equations, and $LaTeX: a_0$ is the fractional part of the same linear combination of the right-hand sides). Also, let $LaTeX: c = y - \lfloor y \rfloor$ (fractional part of $LaTeX: y$). Then, Gomory's cut is:
$LaTeX: a^T x + c^T s \ge a_0.$
The vector $LaTeX: y$ is chosen such that $LaTeX: a_0 > 0$ and the current solution (with $LaTeX: x = 0$) violates this inequality in the LP relaxation.