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

Julian Hall (jajhalled.ac.uk)
Ken McKinnon (K.I.M.McKinnoned.ac.uk)

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.

Keywords: Linear programming, revised simplex method, hyper-sparsity

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: University of Edinburgh School of Mathematics October 2002

Download: [Postscript][Compressed Postscript][PDF]

Entry Submitted: 11/01/2000
Entry Accepted: 11/01/2000
Entry Last Modified: 01/08/2004

Modify/Update this entry