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

###
Invited seminar at CERFACS: 9th October 2003

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

####
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.

**Slides:**

PDF HyperSparsity_09.10.03.pdf.