Optimization Online


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

Julian Hall (jajhall***at***ed.ac.uk)
Ken McKinnon (K.I.M.McKinnon***at***ed.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society