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

Hyper-sparsity October 2002

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

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.

Key words: Linear programming, revised simplex method, hyper-sparsity

Awarded the prize for the best paper of 2005 in Computational Optimization and Applications.

PDF HyperSparsityOctober2002.pdf

Related Publications
Technical Report MS 99-014
Technical Report MS 00-015
COAP Prize 2005

Wholly reworked version of Technical Report MS 00-015
Also available from Optimization Online
Computational Optimization and Applications 32(3), 259-283, 2005.