Linear program, entering/leaving variables & exit conditions

Question

I'm trying to implement my own Simplex solver and I'm encountering some issues. When choosing the leaving variable, one is supposed to pick the element with the smallest positive $b_i/x_{i,j}$ where $j$ is the entering column chosen earlier. Are there more constraints for a pivot to be valid?

In the (maximizing) example below my implementation chooses S16 (slack var) to leave and X5 to enter:

                    C  -1  -1  -1  -1   -0.5  -100  -100  -100  -100  -100  -100    0    0    0    0    0
   Basis  Cb        b  X1  X2  X3  X4  >> X5    X6    X7    X8    X9   X10   X11  S12  S13  S14  S15  S16
      X2  -1        0  -1   1   0   0    0.5     0     0     0     0     0     0    0    0    0    0    0
      X4  -1        0  -1   0   0   1    0.5     0     0     0     0     0     0    0    0    0    0    0
      X3  -1        0  -1   0   1   0      0     0     0     0     0     0     0    0    0    0    0    0
     S12   0        1   1   0   0   0      0     0     0     0     0     0     0    1    0    0    0    0
     S13   0        1   1   0   0   0   -0.5     0     0     0     0     0     0    0    1    0    0    0
     S14   0        1   1   0   0   0      0     0     0     0     0     0     0    0    0    1    0    0
     S15   0        1   1   0   0   0   -0.5     0     0     0     0     0     0    0    0    0    1    0
  << S16   0        1   0   0   0   0      1     0     0     0     0     0     0    0    0    0    0    1
                Z = 0   3                 -1     0     0     0     0     0     0
              Cj - Zj  -4                0.5  -100  -100  -100  -100  -100  -100

This causes two of the $b$ values to become negative, which clearly isn't a valid solution.

                     C  -1  -1  -1  -1  -0.5  -100  -100  -100  -100  -100  -100    0    0    0    0     0
  Basis    Cb        b  X1  X2  X3  X4    X5    X6    X7    X8    X9   X10   X11  S12  S13  S14  S15   S16
     X2    -1     -0.5  -1   1   0   0     0     0     0     0     0     0     0    0    0    0    0  -0.5
     X4    -1     -0.5  -1   0   0   1     0     0     0     0     0     0     0    0    0    0    0  -0.5
     X3    -1        0  -1   0   1   0     0     0     0     0     0     0     0    0    0    0    0     0
    S12     0        1   1   0   0   0     0     0     0     0     0     0     0    1    0    0    0     0
    S13     0      1.5   1   0   0   0     0     0     0     0     0     0     0    0    1    0    0   0.5
    S14     0        1   1   0   0   0     0     0     0     0     0     0     0    0    0    1    0     0
    S15     0      1.5   1   0   0   0     0     0     0     0     0     0     0    0    0    0    1   0.5
     X5  -0.5        1   0   0   0   0     1     0     0     0     0     0     0    0    0    0    0     1
               Z = 0.5   3                       0     0     0     0     0     0                       0.5
               Cj - Zj  -4                    -100  -100  -100  -100  -100  -100                      -0.5

The $C_j - Z_j = 0.5$ would seem to suggest there is a better solution, but I am clearly missing some exit condition here as the solution before the pivot is already optimal.

score 2 · Accepted Answer · answered Aug 20 '21 at 16:57

The rule is not precisely "pick a leaving variable with the smallest positive ratio". There are two mostly-equivalent rules:

Pick a leaving variable with the smallest nonnegative ratio.
Consider all variables with a positive value in the entering variable's column. Out of those, pick a leaving variable with the smallest ratio.

Sometimes there's a tie, in which case any way to break the tie gives us another valid tableau after we pivot.

Moreover, when the ratio is $0$, you are doing degenerate pivoting: a pivoting step that changes the basis but does not actually change the solution (or the objective value). This is not inherently a problem, but it does mean that you should be worried about cycling: you could get stuck in a loop of degenerate pivoting steps and never make progress.

There are all sorts of refinements to the simplex pivoting rule that tell you how to break ties in an effort to avoid this.

Oh, interesting. So in my case I really should be pivoting with the rows containing $x_2$ or $x_4$? — Chris, Aug 20 '21 at 17:04
Yes, that is correct. (The fact that those variables became negative when you pivoted is another hint.) — Misha Lavrov, Aug 20 '21 at 17:05
Yeah something was definitely off, but couldn't quite put my finger on why. I changed my code and that seems to have helped! Cheers mate! — Chris, Aug 20 '21 at 17:08

Linear program, entering/leaving variables & exit conditions

1 Answers1