This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by McBride, R. D. Articles by Mamer, J. W. Search for Related Content

Implementing an LU Factorization for the Embedded Network Simplex Algorithm

Marshall School of Business, University of Southern California, Los Angeles, California 90089-0809, USA.
Anderson Graduate School of Management, University of California, Los Angeles, 110 Westwood Plaza, Suite D518, Box 951481, Los Angeles, California 90095-1481, USA.
mcbride{at}usc.edu
john.mamer{at}anderson.ucla.edu

This paper presents an LU factorization specialized for embedded network simplex algorithms. Specializing the LU factorization in this fashion poses a challenge as the embedded network algorithm uses a very compressed working basis inverse. Using publicly available test problems, we demonstrate the impact of this factorization on the EMNET implementation of the embedded network simplex algorithm. We also compare the impact of the LU factorization when coupled with recent advances in starting, pricing, and basis reduction that have already been implemented in EMNET. We demonstrate that this LU factorization is a vital component of EMNET and offers significant performance improvement for virtually all EMNET configurations. To place our results in context, we compare EMNET’s performance with CPLEX.

Key words: optimization; networks; multicommodity
History: received January 2003; revised September 2003; accepted March 2004.