What after Gomory Cut in Linear Programming?

Question

After applying Gomory Cut (to remove the non-integer solution) in Linear Programming, I don't really know what to do with the new constraint that I get as a result. I have tried to add the new constraint to the most-recent tableau that there is, but I don't know how to proceed since the indexes of the objective function (last row in the tableau) remain positive which indicates that we have the optimal solution (which was the non-integer one...).

Most-recent tableau:

	x_(1)	x_(2)	s_(1)	s_(2)	s_(3)	z
r_(1)	1	0	2/7	-1/7	0	0	12/7
r_(2)	0	1	-1/7	5/21	0	0	15/7
r_(3)	0	0	-2/7	-4/21	1	0	20/7
d	0	0	1/7	9/21	0	1	69/7

New equation to remove the non-integer solution: x_1 - s_2 - 1 <= 0

But how can I continue with the tableau and the new constraint? Or should I put it in the tableau of the previous iteration?

(P.S, the objective function is of the form $$ z=c^T x \Leftrightarrow z-c^T x=0 $$ and in the last row of the tableau the indices represent the $$ -c^T $$

Answer 1

The new inequality, in equational form, is $x_1 - s_2 + s_4 = 1$.

However, we cannot add it to the tableau in that form, because $x_1$ is basic. We must subtract the top row, $x_1 + \frac27s_1 - \frac17 s_2 = \frac{12}{7}$, from this new equation, getting $-\frac27 s_1 - \frac67s_2 + s_4 = -\frac57$.

\begin{array}{rrrrrrr|r} x_1 &x_2 &s_1 &s_2 &s_3 &s_4 &z &\\ \hline 1 &0 &2/7 &-1/7 &0 &0 &0 &12/7\\ 0 &1 &-1/7 &5/21 &0 &0 &0 &15/7\\ 0 &0 &-2/7 &-4/21 &1 &0 &0 &20/7\\ 0 &0 &-2/7 &-6/7 &0 &1 &0 &-5/7\\ \hline 0 &0 &1/7 &9/21 &0 &0 &1 &69/7 \end{array}

Now the tableau has nonnegative coefficients in the final row, but it is not feasible: the basic solution is $x_1 = \frac{12}{7}$, $x_2 = \frac{15}{7}$, $s_3 = \frac{20}{7}$, and $s_4 = -\frac57$. So we can use the dual simplex method to restore feasibility.

In the dual simplex method, instead of choosing an entering variable based on the reduced costs, and then choosing a leaving variable to preserve feasibility, we do the opposite:

1. We will choose $s_4$ to be our leaving variable, because it is not feasible.
2. Our entering variable needs to have a negative coefficient in $s_4$'s row, so that dividing by that negative coefficient restores feasibility in the row we chose. So the entering variable could be $s_1$ or $s_2$.
3. To choose between them, compare the ratios $\frac{1/7}{2/7} = \frac12$ and $\frac{9/21}{6/7} = \frac12$ between $s_4$'s row and the bottom row. In this case, they're equal, so it doesn't matter which we choose; in general, we'd pick the variable with the smallest ratio.

A pivoting step where $s_1$ (say) enters and $s_4$ leaves is done in the same way as the ordinary simplex method:

\begin{array}{rrrrrrr|r} x_1 &x_2 &s_1 &s_2 &s_3 &s_4 &z &\\ \hline 1 &0 &0 &-1 &0 &1 &0 &1\\ 0 &1 &0 &2/3 &0 &-1/2 &0 &5/2\\ 0 &0 &0 &2/3 &1 &-1 &0 &25/7\\ 0 &0 &1 &3 &0 &-7/2 &0 &5/2\\ \hline 0 &0 &9 &0 &0 &1/2 &1 &19/2 \end{array}

Here, one pivot has restored feasibility (in general, many steps could be required), so we've finished solving our new LP. Because we still don't have an integer solution, we should add another cutting plane and continue in the same way.