Eingang zum Volltext

Urheberrechtshinweis / Copyright notice

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URL: http://opus.kobv.de/zib/volltexte/2009/1188/

Luce, Robert ; Duintjer Tebbens, Jurjen ; Liesen, Jörg ; Nabben, Robert ; Grötschel, Martin ; Koch, Thorsten ; Schenk, Olaf
TU Berlin, Zuse Institute Berlin, University of Basel

On the Factorization of Simplex Basis Matrices

pdf-Format:
Dokument 1.pdf (508 KB)

Kurzfassung in Englisch

In the simplex algorithm, solving linear systems with the basis matrix and its transpose accounts for a large part of the total computation time.
We investigate various methods from modern numerical linear algebra to improve the computation speed of the basis updates arising in LPs. The experiments are executed on a large real-world test set.

The most widely used solution technique is sparse LU factorization, paired with an updating scheme that allows to use the factors over several iterations. Clearly, small number of fill-in elements in the LU factors is critical for the overall performance.

Using a wide range of LPs we show numerically that after a simple permutation the non-triangular part of the basis matrix is so small, that the whole matrix can be factorized with (relative) fill-in close to the optimum. This permutation has been exploited by simplex practitioners for many years. But to our knowledge no systematic numerical study has been published that demonstrates the effective reduction to a surprisingly small non-triangular problem, even for large scale LPs.

For the factorization of the non-triangular part most existing simplex codes use some variant of dynamic Markowitz pivoting, which originated in the late 1950s. We also show numerically that, in terms of fill-in and in the simplex context, dynamic Markowitz is quite consistently superior to other, more recently developed techniques.

MSC - Klassifikation 65F05
MSC - Klassifikation 90C05
Abteilung: Optimierung
DDC-Sachgruppe: Mathematik
Dokumentart: ZIB-Report
Schriftenreihe: ZIB-Report
Band Nummer: 09-24
ISBN: 1438-0064
Sprache: Englisch
Erstellungsjahr: 2009
Publikationsdatum: 29.07.2009
Bemerkung: printed version not available / keine gedruckte Version

Metadatensuche | Volltextsuche | Browsen | Die neuesten Publikationen | Veröffentlichen
Fragen und Anregungen an bibliothek@zib.de
Letzte Änderung: