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.