Exploiting ultra-sparsity in the revised simplex method
Contributed talk at OR60: The 60th OR Society Conference, 11-13 September 2018
Julian Hall
Abstract
The revised simplex method is generally the technique of choice when solving large sparse linear programming problems, and computational efficiency is driven by the need to compute rows and columns of the standard simplex tableau. Problems for which these vectors are sparse are said to exhibit hyper-sparsity, and techniques to exploit this computationally were developed about 20 years ago. However, for some problems the degree of hyper-sparsity is such that these techniques may be cache inefficient. This talk will discuss techniques by which such ultra-sparsity may be exploited with the aim of gaining further performance improvement.