Hope everything is operating smoothly for everyone here. I am working on a simple problem involving Gomory cutting planes and am having some trouble.
Problem
Consider the following LPP:
\begin{alignat*}{4}
\text{Maximize} \quad \quad \quad x_1 + x_2 & {}{} & & {}{} & & {}{} &\\
\text{Subject To} \quad -3x_1 + 2x_2 & {}\leq{} & 2 & {}{} & & {}{} & & {}{} &\\
4x_1 + x_2 & {}\leq{} & 8 & {}{} & & {}{} & & {}{} &\\
x_1, x_2 & {}\in{} & \mathbb{N}_0 & {}{} & & {}{} & & {}{} &\\
\end{alignat*}
Employing the Simplex method to solve the LP's relaxation, we arrive at the following optimal tableau:
$$
\begin{array}{c|cccc}
z & x_1 & x_2 & x_3 & x_4 & \text{RHS}\\
\hline
0 & 0 & 1 & \frac{4}{11} & \frac{3}{11} & \frac{32}{11} \\
0 & 1 & 0 & -\frac{1}{11} & \frac{2}{11} & \frac{14}{11} \\
\hline
-1 & 0 & 0 & -\frac{3}{11} & -\frac{5}{11} & -\frac{46}{11}
\end{array}
$$
Q: Find two Gomory cutting planes that "chop off" the optimal solution to the LP relaxation for this problem, one using the first row and the other using the second row of the tableau.
My Attempt
We know $x_3 = 2 + 3x_1 – 2x_2$ and $x_4 = 8 – 4x_1 + x_2$. Using the first row of the tableau, we see that $$ \text{frac}(\frac{4}{11})x_3 + \text{frac}(\frac{3}{11})x_4 \geq \text{frac}(\frac{32}{11}) \implies \frac{4}{11}x_3 + \frac{3}{11}x_4 \geq \frac{32}{11} – \bigg\lfloor \frac{32}{11} \bigg\rfloor = \frac{10}{11}$$ We can rewrite this inequality equation in terms of $x_4$, so $x_4 = 8 – 4x_1 + x_2 \geq -\frac{4}{3}x_3 + \frac{10}{3}$. Since $x_3= 2 + 3x_1 – 2x_2$, this implies that $x_2 \leq 2$. This is the first cut (not sure if I am doing this correctly). Now we can look at the second row of the tableau and see that $$ \text{frac}(-\frac{1}{11})x_3 + \text{frac}(\frac{2}{11})x_4 \geq \text{frac}(\frac{14}{11}) \implies -\frac{1}{11}x_3 + \frac{2}{11}x_4 \geq \frac{14}{11} – \bigg\lfloor \frac{14}{11} \bigg\rfloor = \frac{3}{11}$$
Proceeding in a similar manner as before, we can rewrite $x_3$ in terms of $x_4$, which gives us $x_3 \geq -3 + 2x_4$. Since $x_3 = 2 + 3x_1 – 2x_2 \geq -3 + 2x_4$ we get that $x_1 \geq 1$, which forms the second cutting plane (again, not sure if what I've done is accurate or right in any case).
So, the first cutting plane is $x_2 \leq 2$ and the second cutting plane is $x_1 \geq 1$.
Best Answer
So you have: $$x_1 - \frac{1}{11}x_3 + \frac{2}{11} x_4 = \frac{14}{11}. \qquad (1)$$ Since all variables are nonnegative, we can round down the coefficients and obtain a valid inequality: $$x_1 - x_3 \leq \frac{14}{11}.$$ Since $x_1$ and $x_3$ are integer, this inequality is the same as: $$x_1 - x_3 \leq 1.$$ If you subtract this from $(1)$, you obtain: $$\frac{10}{11}x_3 + \frac{2}{11} x_4 \geq \frac{3}{11}.$$ Since $x_3 = 2+3x_1-2x_2$ and $x_4=8-4x_1-x_2$, this becomes: $$\frac{10}{11}(2+3x_1-2x_2) + \frac{2}{11} (8-4x_1-x_2) \geq -\frac{3}{11},$$ which simplifies to the cut: $$2x_1 - 2x_2 \geq -3.$$