A review of LU factorisation in the simplex algorithm

Joseph M. Elble and Nikolaos V. Sahinidis

International Journal of Mathematics in Operational Research, 2012, vol. 4, issue 4, 319-365

Abstract: This paper reviews the computational aspects of the LU factorisation of large-scale linear optimisation bases. In the simplex algorithm, the solution of two linear systems, involving a square basis matrix and its transpose, accounts for a large portion of the computation time. The most widely used solution technique is LU factorisation and accompanying update routines. The utilisation of a column replacement update procedure means that a given factorisation may be kept over a large number of simplex iterations. Therefore, a significant emphasis is placed on the sparsity of the LU factors. This emphasis means that a suitable factorisation routine must be chosen with care. A review of LU factorisation is offered, including stability monitoring and analysis, sparsity analysis, error analysis, algorithmic aspects, and state-of-the-art LU factorisation routines.

Keywords: simplex algorithm; LU factorisation; linear optimisation; LU decomposition. (search for similar items in EconPapers)
Date: 2012
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=48900 (text/html)
Access to full text is restricted to subscribers.

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:ids:ijmore:v:4:y:2012:i:4:p:319-365

Access Statistics for this article

More articles in International Journal of Mathematics in Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().