Exploiting hyper-sparsity in the revised simplex method

Technical Report MS 99-014

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. In each iteration of the method, three matrix-vector products are formed and, even for many sparse problems, the result is typically dense. However it is demonstrated in this paper that for a significant number of practical problems, the result of one or more of these three operations is usually sparse. In this paper, this property of a problem is referred to as hyper-sparsity. Analysis of the commonly-used computational techniques for each of the components of the revised simplex method shows them to be inefficient when applied to problems which exhibit hyper-sparsity and techniques which exploit hyper-sparsity are developed. For such problems, the performance of the revised simplex method when using these techniques is demonstrated to be many times faster than a commercial implementation of both the revised simplex method and barrier method. When applied to network problems, the revised simplex method using these techniques is demonstrated to be comparable in speed to an efficient implementation of the network simplex method.

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

PDF MS9914.pdf
Related Publications
Technical Report MS 00-015
Hyper-sparsity October 2002
COAP Prize 2005