ASYNPLEX, an asynchronous parallel revised simplex algorithm

Technical Report MS 95-050a

J.A.J. Hall and K.I.M. McKinnon

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.

PDF 95050a.pdf
This is a revised version of MS 95-050
This version was recommended in July 1997 for publication in Annals of Operations Research.
A second revised version MS 95-050b was requested by the editor-in-chief of Annals of Operations Research.
Related Publications
Technical Report MS 96-012
Technical Report MSR 92-13