Making progress during a stall in the simplex algorithm

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.

Recommendations

Cites work

Cited in

(11)

Describes a project that uses

Uses Software

MINOS

This page was built for publication: Making progress during a stall in the simplex algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1116654)