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 shar ed memory multiprocessor or MIMD computer with fast inter-processor co mmunication. The method overlaps simplex iterations on different proce ssors. Candidates to enter the basis are tentatively selected using re duced costs which may be out of date. Later, the up-to-date reduced co sts of the tentative candidates are calculated and candidates are eith er discarded or accepted to enter the basis. The implementation of thi s algorithm on a Gray T3D is described and results demonstrating signi ficant speed-up are presented.