A Spike Collective Dynamic Factorization Algorithm for the Simplex Method

Richard D. McBride
Additional contact information
Richard D. McBride: University of Southern California

Management Science, 1978, vol. 24, issue 10, 1031-1042

Abstract: A dynamic factorization algorithm is developed which uses a partition of the basis to permit the simplex method to be executed from a small working inverse and a small, sparse triangular submatrix of the basis. This partition is maintained dynamically using spike swapping in a way which seeks to keep the size of the working inverse as small as possible. The algorithm is intended for use in solving general large scale linear programming problems. It is especially well suited for problems whose simplex basis has a small number of spikes after application of the Hellerman and Rarick P 3 procedure. Preliminary computation experience and direct comparison with Reid's sparsity-exploiting variant of the Bartels-Golub decomposition for LP bases indicate that a significant reduction is obtained with the dynamic factorization approach in the nonzero elements needed to represent the basis inverse. For all bases considered the number of nonzero elements needed to represent the inverse immediately prior to rein version is reduced by a factor of 1.7 to 20.

Date: 1978
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.24.10.1031 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:24:y:1978:i:10:p:1031-1042

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().