Let \((IP)\) denote the following integer linear programming problem: \[\begin{array}{rrcrcrcl} \min & x_1 & + & 2x_2 & & & \\ \mbox{s.t.} & 4x_1 & - & 3x_2 & + & 2x_3 & = & 1 \\ & x_1 & + & 3x_2 & + & 2x_3 & = & 2 \\ & x_1 & , & x_2 & , & x_3 & \geq & 0 \\ & x_1 & , & x_2 & , & x_3 & \in & \mathbb{Z}. \end{array}\] An optimal solution to the linear programming relaxation of \((IP)\) is \(\begin{bmatrix} x_1 \\x_2\\x_3\end{bmatrix} = \begin{bmatrix} 0 \\ \frac{1}{6} \\ \frac{3}{4}\end{bmatrix}\). Since this solution is fractional, we could proceed with the branch-and-bound method. However, we look at another popular integer programming technique called cutting-plane method.
From the equality constraint \(4x_1 - 3x_2 + 2x_3 = 1\) and the inequality \(x_2 \geq 0\), we see that all feasible solutions must satisfy \(4x_1 - 2x_2 + 2x_3 \geq 1\), or equivalently, \[2x_1 - x_2 + x_3 \geq \frac{1}{2}.\] But \(x_1\), \(x_2\), and \(x_3\) are required to be integers. Hence, \(2x_1 - x_2 + x_3\) is an integer for all all feasible solutions of \((IP)\). Thus, all feasible solutions satisfies \[2x_1 - x_2 + x_3 \geq 1.\] Adding this inequality to the LP relaxation of \((IP)\) results in an infeasible problem. To see this, note that \(-\frac{7}{3}\) times \(4x_1 - 3x_2 + 2x_3 = 1\) plus \(-\frac{2}{3}\) times \(x_1 + 3x_2 + 2x_3 = 2\) plus \(5\) times \(2x_1 - x_2 + x_3 \geq 1\) gives \(-x_3 \geq \frac{4}{3},\) implying that \(x_3 \leq -\frac{4}{3}\). However, \(x_3 \geq 0\) is also a constraint. This is impossible. Thus, \((IP)\) is infeasible.
More generally, let \(n\) be a positive integer and let \(m\), \(m'\), and \(m''\) be nonnegative integers. Given the following integer linear programming problem \[ \begin{array}{rl} \min & \mathbf{c}^\mathsf{T} \mathbf{x}\\ (IP)~~~~\mbox{s.t.} & \mathbf{A}\mathbf{x} \geq \mathbf{b} \\ & \mathbf{A}'\mathbf{x} \leq \mathbf{b}' \\ & \mathbf{A}''\mathbf{x} = \mathbf{b}'' \\ & \mathbf{x} \in \mathbb{Z}^n \end{array} \] where \(\mathbf{c} \in \mathbb{R}^{n}\), \(\mathbf{A} \in \mathbb{R}^{m\times n}\), \(\mathbf{A}' \in \mathbb{R}^{m' \times n}\), \(\mathbf{A}'' \in \mathbb{R}^{m'' \times n}\), \(\mathbf{b} \in \mathbb{R}^{m}\), \(\mathbf{b}' \in \mathbb{R}^{m'}\), and \(\mathbf{b}'' \in \mathbb{R}^{m''}\), if \(\mathbf{a}^\mathsf{T} \mathbf{x} \geq \mathbf{v}\) is such that \(\mathbf{a} \in \mathbb{Z}^n\) and \[\mathbf{a}^\mathsf{T} = \mathbf{d}^\mathsf{T} \mathbf{A} + {\mathbf{d}'}^\mathsf{T} \mathbf{A}' + {\mathbf{d}''}^\mathsf{T} \mathbf{A}'',~ v = \mathbf{d}^\mathsf{T} \mathbf{b} + {\mathbf{d}'}^\mathsf{T} \mathbf{b}' + {\mathbf{d}''}^\mathsf{T} \mathbf{b}''\] for some \(\mathbf{d} \in \mathbb{R}^m\), \(\mathbf{d}' \in \mathbb{R}^{m'}\), and \(\mathbf{d}'' \in \mathbb{R}^{m''}\) with \(\mathbf{d} \geq \mathbf{0}\) and \(\mathbf{d}' \leq \mathbf{0}\), then every feasible solution to \((IP)\) satisfies the inequality \(\mathbf{a}^\mathsf{T} \mathbf{x} \geq \lceil \mathbf{v}\rceil\). The inequality \(\mathbf{a}^\mathsf{T} \mathbf{x} \geq \lceil \mathbf{v}\rceil\) is known as a Chvátal-Gomory cut.
Similarly, if \(\mathbf{a}^\mathsf{T} \mathbf{x} \leq \mathbf{v}\) is such that \(\mathbf{a} \in \mathbb{Z}^n\) and \[\mathbf{a}^\mathsf{T} = \mathbf{d}^\mathsf{T} \mathbf{A} + {\mathbf{d}'}^\mathsf{T} \mathbf{A}' + {\mathbf{d}''}^\mathsf{T} \mathbf{A}'',~ v = \mathbf{d}^\mathsf{T} \mathbf{b} + {\mathbf{d}'}^\mathsf{T} \mathbf{b}' + {\mathbf{d}''}^\mathsf{T} \mathbf{b}''\] for some \(\mathbf{d} \in \mathbb{R}^m\), \(\mathbf{d}' \in \mathbb{R}^{m'}\), and \(\mathbf{d}'' \in \mathbb{R}^{m''}\) with \(\mathbf{d} \leq \mathbf{0}\) and \(\mathbf{d}' \geq \mathbf{0}\), the inequality \(\mathbf{a}^\mathsf{T} \mathbf{x} \leq \lfloor \mathbf{v}\rfloor\) is also a Chvátal-Gomory cut (CG-cut).
Thus, the key to obtaining a CG-cut is to come up with a linear combination of the constraints that gives an inequality with integer coefficients for the variables and a fractional constant term. However, it is not immediately clear how to come up with the multipliers \(\mathbf{d}\), \(\mathbf{d}'\), and \(\mathbf{d}''\) above. We now look at a method for obtaining CG-cuts in the case when the problem is in standard equality form is described.
Let \((IP)\) denote the integer linear programming problem \[ \begin{array}{rl} \min & \mathbf{c}^\mathsf{T} \mathbf{x}\\ \mbox{s.t.} & \mathbf{A}\mathbf{x} = \mathbf{b} \\ & \mathbf{x} \geq \mathbf{0} \\ & \mathbf{x} \in \mathbb{Z}^n \end{array} \] where \(\mathbf{A} \in \mathbb{R}^{m\times n}\) has rank \(m\), \(\mathbf{b} \in \mathbb{R}^{m}\), and \(\mathbf{c} \in \mathbb{R}^{n}\). Let \(B\) be a basis that determines the basic feasible solution \(\mathbf{x}^*\) for the linear programming relaxation.
Suppose that \(i \in B\) is such that \(x^*_i \notin \mathbb{Z}\) and the \(x_i\)-row of the tableau associated with \(B\) is \(x_i + \sum_{j \in N} \bar{a}_{ij} x_j = \bar{b}_i\) where \(N = \{1,\ldots,n\}\backslash B\). Then \(x_i + \sum_{j \in N} \lfloor \bar{a}_{ij}\rfloor x_j \leq \lfloor\bar{b}_i\rfloor\) is a CG-cut that is not satisfied by \(\mathbf{x}^*\).
To see this, note that \(\mathbf{x}^*\) does not satisfy \(x_i + \sum_{j \in N} \lfloor \bar{a}_{ij}\rfloor x_j \leq \lfloor\bar{b}_i\rfloor\) because \(x^*_j = 0\) for all \(j \in N\) and that \(x^*_i = \bar{b}_i \gt \lfloor \bar{b}_i\rfloor\).
Since the tableau associated with \(B\) is obtained from \(\mathbf{A}\mathbf{x} = \mathbf{b}\) by performing a finite number elementary row operations, there exists \(\mathbf{d} \in \mathbb{R}^m\) such that the \(x_i\)-row is given by \(\mathbf{d}^\mathsf{T} \mathbf{A} \mathbf{x} = \mathbf{d}^\mathsf{T} \mathbf{b}\). For each \(j \in N\), let \(f_j = \lfloor \bar{a}_{ij} \rfloor - \bar{a}_{ij}\). Since \(f_j \leq 0\), \(f_j\) times \( x_j \geq 0\) gives \(f_j x_j \leq 0\) for all \(j \in N\). Then adding \(\mathbf{d}^\mathsf{T} \mathbf{A} \mathbf{x} = \mathbf{d}^\mathsf{T} \mathbf{b}\) and \(f_j\) times \( x_j \geq 0\) for all \(j \in N\) gives \(x_i + \sum_{j \in N} \lfloor \bar{a}_{ij}\rfloor x_j \leq \bar{b}_i\). Since the coefficients on the left-hand side are integers, \(x_i + \sum_{j \in N} \lfloor \bar{a}_{ij}\rfloor x_j \leq \lfloor\bar{b}_i\rfloor\) is a CG-cut.
Remark. Note that the inequality \(x_i + \sum_{j \in N} \lfloor \bar{a}_{ij}\rfloor x_j \leq \lfloor\bar{b}_i\rfloor\) can be added to \((IP)\) as \(x_i + \sum_{j \in N} \lfloor \bar{a}_{ij}\rfloor x_j + s_i = \lfloor\bar{b}_i\rfloor\) where \(s_i\) is a nonnegative integer variable. Thus, we end up with a problem of the same form as \((IP)\). Furthermore, we can continue with the dual simplex method. Hence, the process can be repeated.
We will illustrate the method by obtaining CG-cuts for the example at the beginning.
The basis \(B = \{2,3\}\) determines the optimal solution \(\begin{bmatrix} 0 \\ \frac{1}{6} \\ \frac{3}{4}\end{bmatrix}\) to the linear programming relaxation of \((IP)\). The tableau associated with \(B\) is: \[\begin{array}{rcrcrcrcl} z & -& 2x_1 & & & & & = & \frac{1}{3} \\ & & -\frac{1}{2}x_1 & + & x_2 & & & = & \frac{1}{6} \\ & & \frac{5}{4}x_1 & & & + & x_3 & = & \frac{3}{4} \\ \end{array}\] From the \(x_2\)-row, we obtain the CG-cut \[\left\lfloor -\frac{1}{2} \right\rfloor x_1 + x_2 \leq \left\lfloor\frac{1}{6}\right\rfloor\] which is \[-x_1 + x_2 \leq 0.\]
From the \(x_3\)-row, we obtain the CG-cut \[\left\lfloor \frac{5}{4}\right\rfloor x_1 + x_3 \leq \left\lfloor \frac{3}{4}\right\rfloor\] which is \[x_1 + x_3 \leq 0.\]
Remarks.
Note that adding \( -x_1 + x_2 \leq 0\) to the linear programming relaxation of \((P)\) does not result in an infeasible problem but adding \(x_1 + x_3 \leq 0\) does.
Technically, one can also obtain a CG-cut from the \(z\)-row. In the example above, it would be \(z - 2x_1 \leq 0\). However, CG-cuts obtained from the \(z\)-row are usually not very helpful.