#
Hyper-sparsity in the revised simplex method and how to exploit it

###
Contributed talk at the Dundee Numerical Analysis Conference: 25th June 2003

###
J. A. J. Hall and K. I. M. McKinnon

####
Abstract

The revised simplex method is often the method of choice when solving large scale sparse linear programming problems, particularly when a family of closely-related problems is to be solved. Each iteration of the revised simplex method requires the solution of two linear systems and a matrix vector product. For a significant number of practical problems the result of one or more of these operations is usually sparse, a property we call hyper-sparsity. Analysis of the commonly-used techniques for implementing each step of the revised simplex method shows them to be inefficient when hyper-sparsity is present. Techniques to exploit hyper-sparsity are developed and their performance is compared with the standard techniques. For the subset of our test problems that exhibits hyper-sparsity, the average speedup in solution time is 5.2 when these techniques are used. For this problem set our implementation of the revised simplex method which exploits hyper-sparsity is shown to be competitive with the leading commercial solver and significantly faster than the leading public-domain solver.

**Slides:**

Postscript HyperSparsity_25.06.03.ps

Compressed Postscript HyperSparsity_25.06.03.ps.Z

G-Zipped Postscript HyperSparsity_25.06.03.ps.gz

PDF HyperSparsity_25.06.03.pdf
Note that the postscript version is of finer resolution.

Last modified: