Making progress during a stall in the simplex algorithm (Q1116654)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Making progress during a stall in the simplex algorithm |
scientific article |
Statements
Making progress during a stall in the simplex algorithm (English)
0 references
1989
0 references
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.
0 references
pivoting rule
0 references
degeneracy
0 references
linear programming
0 references
random numbers
0 references
Computational tests
0 references
simplex method
0 references
0 references