Application of the cutting plane algorithm with Gomory cuts to solve a particular integer program Apply the cutting plane algorithm with Gomory cuts (with pen and paper) to the following integer program:
$$ \left\{ x_1 + x_2 \mid 6x_1 + x_2 \leq 4, 3x_1 \geq 1, x_1,x_2 \in \mathbb{Z}, x_1,x_2 \geq 0 \right\}. $$
The professor teaching the course said it takes very few iterations to solve this problem and it can therefore be done by hand; he also gave an example to illustrate the algorithm, which was confusing to me. If someone could illustrate the application of the algorithm to the above problem, that would be fantastic!
 A: Suppose we have a feasible region defined by one constraint and nonnegative integer variables:
\begin{align}
\sum_{j=1}^n& a_jx_j\leqslant b\\\tag1
x_j\in&\mathbb Z_+,\ j\in\{1,2,\ldots,n\}.
\end{align}
Assume that $b$ is fractional (i.e. not an integer). Note that the inequality $\sum_{j=1}^n \lfloor a_j\rfloor x_j\leqslant b$ is valid for $(1)$. Observe that if $\hat x$ satisfies $(1)$ then by definition it is a nonnegative vector. Therefore $\sum_{j=1}^n\lfloor a_j\rfloor \hat x_j \leqslant \sum_{j=1}^n a_j\hat x_j$, and since $\hat x$ satisfies $(1)$ then $\sum_{j=1}^n a_j\hat x_j\leqslant b$. Thus $\sum_{j=1}^n \lfloor a_j\rfloor \hat x_j\leqslant\sum_{j=1}^n a_j\hat x_j\leqslant b$ and therefore $\sum_{j=1}^n \lfloor a_j\rfloor x_j\leqslant b$ is a valid inequality for $(1)$ that does not cut off feasible integer points.
Now observe that $\lfloor a_j\rfloor$ is an integer. If $x$ is an integer vector that satisfies $(1)$ then $\sum_{j=1}^n\lfloor a_j\rfloor x_j$ must be an integer. Therefore we can obtain the inequality $$\sum_{j=1}^n \lfloor a_j\rfloor x_j\leqslant \lfloor b\rfloor.\tag2$$ This is called the Gomory fractional inequality.
Consider the integer program
\begin{align}
\min&\quad x_1-2x_2\\
\mathrm{s.t.}&\quad -4x_1+6x_2\leqslant 9\\
&\quad x_1+x_2\leqslant 4\\
&\quad x_1,x_2\geqslant0\\
&\quad x_1,x_2\in\mathbb Z
\end{align}
In standard form, this becomes
\begin{align}
\min&\quad x_1-2x_2\\
\mathrm{s.t.}&\quad -4x_1+6x_2+x_3=9\\
&\quad x_1+x_2+x_4 = 4\\
&\quad x_1,x_2,x_3,x_4\in\mathbb Z\\
&\quad x_1,x_2,x_3,x_4\geqslant 0
\end{align}
We solve the LP relaxation to get $x^* = \left(\frac{15}{10},\frac{25}{10}\right)$. The system $B^{-1}Ax = B^{-1}b$ can be written as
\begin{align}
x_1-\frac1{10}x_3 + \frac35 x_4 &=\frac{15}{10}\\
x_2+\frac1{10}x_3 + \frac25 x_4 &= \frac{25}{10}.
\end{align}
Applying $(2)$ to the second equation, we get $x_2 + \left\lfloor\frac1{10}\right\rfloor + \left\lfloor\frac25\right\rfloor x_4\leqslant\left\lfloor\frac{25}{10}\right\rfloor$ and hence $x_2\leqslant 2$. Adding this to our constraints, in the form of $x_2+x_5=2$ and solving the LP relaxation again, we get $x^*=\left(\frac34,2\right)$. Writing $B^{-1}Ax = B^{-1}b$ we have
\begin{align}
x_1-\frac14x_3+\frac32x_5&=\frac34\\
x_2+x_5&=2.
\end{align}
Apply $(2)$ to the first equation to get $x_1+\left\lfloor\frac{-1}4\right\rfloor x_3 +\left\lfloor\frac 32\right\rfloor x_5\leqslant \left\lfloor \frac34\right\rfloor$, and hence $x_1-x_3+x_5\leqslant 0$. Since $x_2+x_5=2$, we have $x_5=2-x_2$. In terms of the original variables $x_1,x_2$ we get $-3x_1+5x_2\leqslant 7$. Adding this constraint and again solving the LP relaxation, we get $x^*=(1,2)$ which is integer. So it is the optimal solution of the original problem.
