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!
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.