Gomory cut

From Glossary

Jump to: navigation, search


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.


Views
Personal tools