Simplex method: a degenerate case with 0 ratio

Question

Consider the problem

max x
s.t.
x <= 5
-x <= 0

The tableau with the first 2 iterations that continues to cycle infinitely (tableau 1 = 3):

------------
Tableu no. 1

          Z    x1    S1    S2    RHS
          _    __    __    __    ___
    Z     1    -1    0     0      0 
    S1    0     1    1     0      5 
    S2    0    -1    0     1      0 

Z=-0
entering variable: x1
min ratio: -0
leaving variable: S2

------------
Tableu no. 2

          Z    x1    S1    S2    RHS
          _    __    __    __    ___
    Z     1    0     0     -1     0 
    S1    0    0     1      1     5 
    x1    0    1     0     -1     0 

Z=-0
entering variable: S2
min ratio: 0
leaving variable: x1

------------
Tableu no. 3

          Z    x1    S1    S2    RHS
          _    __    __    __    ___
    Z     1    -1    0     0      0 
    S1    0     1    1     0      5 
    S2    0    -1    0     1      0 

When calculative the ratio, if I add epsilon (machine) to RHS, then it's fine (since I ignore negative ratios):

------------
Tableu no. 1

          Z    x1    S1    S2    RHS
          _    __    __    __    ___
    Z     1    -1    0     0      0 
    S1    0     1    1     0      5 
    S2    0    -1    0     1      0 

Z=-0
entering variable: x1
min ratio: 5
leaving variable: S1

------------
Tableu no. 2

          Z    x1    S1    S2    RHS
          _    __    __    __    ___
    Z     1    0     1     0      5 
    x1    0    1     1     0      5 
    S2    0    0     1     1      5 

Z=5
Reached optimum

output:
    {'Z'}    {'x1'}
    {[5]}    {[ 5]}

What exactly is happening here, and why do I need eps?

Or more to the point, how come it's not mentioned in simplex tutorials, and is this the common approach to handle it?

(Note that I can't just ignore 0 ratio since I may miss the optimum in some cases.)

Answer 1

In terms of cycling in degeneracy, what is effectively happening is that the Simplex method is getting caught between multiple constraints that cross at the same intersection and is unable to get out. Once we are in this situation however, we may notice certain cases:

1. Two of the rows have the same right hand-side values, in which we can then deploy Bland's Rule where we pick the first improving column with the smallest subscript and the first feasible row until we're out of the cycle.

2. We can treat the division of zero and a negative number in the denominator as an infeasible direction in the minimum-ratio-test, in other words $\frac{0}{-\alpha}=-0=\infty$ so that we'll never pick that row.

(Note that I can't just ignore $0$ ratio since I may miss the optimum in some cases.)

We can safety ignore the zero ratio as it is a by-product of a redundant constraint that does not contribute to our model. We often do ignore them in order to avoid unnecessary pivots or to prevent cycling, as that's a big issue within models. The only time we do not ignore it is if it’s the only ratio available.

---

To give a visual example of degeneracy, and how it appears graphically, let's look at the model,

$$\max\quad z=2x_1+3x_2$$ Subject to: $$x_1+2x_2\le10$$ $$-x_1+2x_2\le6$$ $$x_1+x_2\le6$$ $$x_1,x_2\ge0$$

This can be graphically represented as such:

With the black-ish region denoting the feasible region of the model, and the top-most point denoting the optimal extreme point. Notice that there are three lines that cross this one extreme point in the model, and this does cause degeneracy in the model by introducing a needless extra pivot once we reach our optimal extreme point. However, if there would exist another constraint that happened to cross this exact same point in the model and constantly trade off non-basic variables with the other degenerate constraint in the model, we'd be stuck in a cycle between two (or more) degenerate constraints.