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