Elaboration of rules for Gomory’s cutting plane algorithm.

Question

The Gomory’s cutting plane algorithm is as follows:

I’m also looking at the theorem:

Theorem 2 (Gomory). Suppose Gomory's algorithm is implemented by:

1. using the lexicographic simplex algorithm for LP solving and
2. deriving Gomory cut from the fractional variable with the smallest index.

Then the algorithm will terminate in finite numbers of iterations.

Now in the example, I have the following optimal LP tableau:

\begin{array} {|r|r|}\hline \text{Basic vars.} & x_1 & x_2 & x_3 & x_4 & x_5 & \\ \hline x_3 & 0 & 0 & 1 & -1/3 & 1/3 & 7/3 \\ \hline x_1 & 1 & 0 & 0 & 1/3 & -1/3 & 5/3 \\ \hline x_2 & 0 & 1 & 0 & 1/3 & 2/3 & 20/3 \\ \hline & 0 & 0 & 0 & -1 & -1 & -15 \\ \hline \end{array}

The example says that I should generate a Gomory’s cut from row $1$ of the tableau, i.e. the one with $x_3$ as the basic variable, as it has the smallest fractional index. But amongst the three basic variables $x_1,x_2,x_3$ that are fractional, shouldn’t $x_1$ be the one with the smallest fractional index? Am I misunderstanding something?

Answer 1

I'm working on this too so I wouldn't trust my answer completely. However, I think you should actually derive a Gomory cut from the fractional variable with the largest index.