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