ASYNPLEX, an asynchronous parallel revised simplex algorithm

This paper describes ASYNPLEX, an asynchronous variant of the revised simplex method which is suitable for parallel implementation on a shared memory multiprocessor of 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.