An Alternative Simplex Criterion Under Degeneracy

When degeneracies occur, the simplex multipliers can no longer be interpreted as derivatives of the optimal value of the current basic feasible solution with respect to a non-basic variable. This paper develops an alternative criterion for entering variables based on directional derivatives. If it is possible to make progress at the next iteration, the criterion is guaranteed to identify a non-basic variable which increases the value of the basic solution. The procedure also suggests an alternative method for determining variables to exit the basis when degeneracies occur. When used in conjunction with normal simplex pivoting at each iteration, the criterion can be implemented by checking signs of appropriate elements in the constraint matrix. Although it cannot be established in general that the procedure eliminates cycling, an example shows that it can reduce stalling and in one instance, at least, prevent cycling.