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