Title: A review of LU factorisation in the simplex algorithm

Authors: Joseph M. Elble; Nikolaos V. Sahinidis

Addresses: Department of Industrial and Enterprise Systems Engineering, University of Illinois at Urbana-Champaign, 104 S. Mathews Ave., Urbana, IL 61801, USA ' Department of Chemical Engineering, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA 15213, USA

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.

DOI: 10.1504/IJMOR.2012.048900

International Journal of Mathematics in Operational Research, 2012 Vol.4 No.4, pp.319 - 365

Published online: 23 Dec 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article