Exploiting Degeneracy In Linear Programming
Original Publication Date: 1980-Jan-01
Included in the Prior Art Database: 2005-Feb-13
The simplex method often performs a large number of degenerate iterations on linear programs encountered in practice. This article studies degeneracy from the point of view of reducing the computational effort per degenerate iteration. First, the simplex method is viewed as performing a sequence of nondegenerate iterations, with the direction of movement at each such iteration being determined by an auxiliary linear program having as many rows as there are degenerate basic variables in the current solution. Then, it is shown that the computations in this setting can be conveniently performed by means of a basic factorization method. In essence, this method achieves its savings during degenerate iterations as follows: 1.