A degeneracy exploiting LU factorization for the simplex method |
| |
Authors: | André F. Perold |
| |
Affiliation: | (1) IBM T.J. Watson Research Center, Yorktown Heights, NY, USA;(2) Present address: Graduate School of Business Administration, Harvard University, 02163 Boston, MA, USA |
| |
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. |
| |
Keywords: | Linear Programming LU Factorization Degeneracy Bartels— Golub Updating |
本文献已被 SpringerLink 等数据库收录! |
|