Permutations in the Factorization of Simplex Bases

Ricardo Fukasawa () and Laurent Poirrier ()
Additional contact information
Ricardo Fukasawa: Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada
Laurent Poirrier: Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada

INFORMS Journal on Computing, 2019, vol. 31, issue 3, 612–632

Abstract: The basis matrices corresponding to consecutive iterations of the simplex method only differ in a single column. This fact is commonly exploited in current linear programming solvers to avoid having to compute a new factorization of the basis at every iteration. Instead, a previous factorization is updated to reflect the modified column. Several methods are known for performing the update, most prominently the Forrest–Tomlin method. We present an alternative algorithm for the special case where the update can be performed purely by permuting rows and columns of the factors. In our experiments, this occurred for about half of the basis updates, and the new algorithm provides a modest reduction in computation time for the dual simplex method.

Keywords: linear programming; simplex method; basis factorization; factorization update (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/ijoc.2018.0862 (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:orijoc:v:31:y:2019:i:3:p:612-632

Access Statistics for this article

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