A degeneracy exploiting LU factorization for the simplex method

Abstract

For general sparse linear programs two of the most efficient implementations of the LU factorization with Bartels-Golub updating are due to Reid and Saunders. This paper presents an alternative approach which achieves fast execution times for degenerate simplex method iterations, especially when used with multiple pricing. The method should have wide applicability since the simplex method performs a high proportion of degenerate iterations on most practical problems. A key feature of Saunders' method is combined with the updating strategy of Reid so as to make the scheme suitable for implementation out of core. Its efficiency is confirmed by experimental results. © 1980 The Mathematical Programming Society.