Implementing an LU Factorization for the Embedded Network Simplex Algorithm

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.