J.A.J. Hall and K.I.M. McKinnon
Abstract
This paper describes ASYNPLEX, an asynchronous variant of the revised
simplex method which is suitable for parallel implementation on a
shared memory multiprocessor or MIMD computer with fast
inter-processor communication. The method overlaps simplex iterations
on different processors. Candidates to enter the basis are tentatively
selected using reduced costs which may be out of date. Later the
up-to-date reduced costs of the tentative candidates are calculated
and candidates are either discarded or accepted to enter the basis.
The implementation of this algorithm on a Cray T3D is described and
results demonstrating significant speed-up are presented.
Key words: Linear programming, revised simplex method, parallelism, Cray T3D.