Promoting hyper-sparsity in the revised simplex method

Contributed talk at APMOD 12, Paderborn, Germany: 28th March 2012

J. A. J. Hall and Q. Huangfu

Abstract

Exploiting hyper-sparsity in the revised simplex method for linear programming (LP) has resulted in the most recent significant performance improvements for efficient solvers. Hitherto, there has been relatively little understanding of how it occurs and how greater degrees of hyper-sparsity may be achieved when solving a given problem. This talk identifies advanced algorithmic techniques for the dual revised simplex method that promote hyper-sparsity, leading to dramatic performance improvements. An analysis of these techniques in the context of network flow optimization gives an insight into why they are so effective.