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

Technical Report MS 00-015

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 many problems, even those for which the constraint matrix is sparse, the results of these operations are usually dense. However it is shown in this paper that there is a significant number of practical problems where the results 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.61 when these techniques are used. For this problem set our implementation of the revised simplex method which exploits hyper-sparsity is shown to be many times faster that a commercial implementation of both the simplex and barrier method. When applied to network problems, our implementation is shown to approach the speed of an efficient implementation of the network simplex method.

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

PDF MS0015.pdf
Related Publications
Technical Report MS 99-014
Hyper-sparsity October 2002
COAP Prize 2005

Submitted to SIAM Journal of Optimization (August 2000).
Appears in The November 2000 edition of Optimization Online as 2000/11/234.html