We now look at a method for obtaining CG-cuts in the case when the problem is in standard equality form.
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.