J.A.J. Hall and K.I.M. McKinnon
Abstract
When solving linear programming problems using the revised simplex method,
two common variants are the incorporation of minor iterations of the
standard simplex method applied to a small subset of the variables and the
use of Devex pricing.
Although the extra work per iteration which is required when updating Devex
weights removes the advantage of using minor iterations in
a serial computation,
the extra work parallelises readily. An asynchronous parallel
algorithm PARSMI is presented in which computational components of the
revised simplex method with Devex pricing are either overlapped or
parallelism is exploited within them. Minor iterations are used to achieve
good load balance and tackle problems caused by limited candidate
persistence. Initial computational results for a six-processor
implementation on a Cray T3D indicate that the algorithm has a significantly
higher iteration rate than an efficient sequential implementation.
Key words: Linear programming, revised simplex method, parallelism, Cray T3D.