Making progress during a stall in the simplex algorithm (Q1116654)

The idea of the parametric method by \textit{S. I. Gass} and \textit{T. L. Saaty} [Naval. Res. Logist. Quart. 2(1), 39-45 (1955; M.R. 23.B477)] is applied to obtain a new rule for resolving degeneracy in linear programming. The original objective cx is replaced by \((c+\theta d)x\), where \(\theta\) is a parameter objective cx is replaced by \((c+\theta d)x\), where \(\theta\) is a parameter and d is a nonnegative vector involving some random numbers. At each iterate t, the incoming variable \(x_ s\) is determined from the reduced cost row \(\bar c+\theta \bar d\) by conditions \(\bar c_ s+\theta \bar d_ s=0,\quad \bar c_ j+\theta \bar d_ j>0\) for nonbasic \(j\neq s\), for some \(\theta =\theta^ t\). This choice of s is unique with probability one because of the presence of random numbers in d. Once s is selected, the choice of the pivot row is arbitrary (under the usual minimum-ratio rule). Since the sequence \(\{\theta^ t\}\) is strictly decreasing, finiteness follows by the usual argument that no basis can occur twice. Computational tests on nine highly degenerated problems showed an approximately 50\% reduction in both the number of iterations and CPU time, compared with the regular simplex method.