Abstract
This paper describes ASYNPLEX, an asynchronous variant of the revised simplex methodwhich is suitable for parallel implementation on a shared memory multiprocessor or MIMDcomputer with fast inter-processor communication. The method overlaps simplex iterationson different processors. Candidates to enter the basis are tentatively selected using reducedcosts which may be out of date. Later, the up-to-date reduced costs of the tentative candidatesare calculated and candidates are either discarded or accepted to enter the basis. The implementationof this algorithm on a Cray T3D is described and results demonstrating significantspeed-up are presented.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R.E. Bixby and A. Martin, Parallelizing the dual simplex method, Technical Report SC-95-45, Konrad-Zuse-Zentrum für Informationstechnik Berlin, 1995.
G.B. Dantzig and W. Orchard-Hays, The product form for the inverse in the simplex method, Math. Comp. 8(1954)64–67.
J. Eckstein, I. Boduroglu, L. Polymenakos and D. Goldfarb, Data-parallel implementations of dense simplex methods on the Connection Machine CM-2, ORSA Journal on Computing 7(1995) 402–416.
J.J.H. Forrest and J.A. Tomlin, Vector processing in the simplex and interior methods for linear programming, Annals of Operations Research 22(1990)71–100.
D.M. Gay, Electronic mail distribution of linear programming test problems, Mathematical Programming Society COAL Newsletter 13(1985)10–12.
P.E. Gill, W. Murray, M.A. Saunders and M.H. Wright, Sparse matrix methods in optimization, SIAM J. Sci. Stat. Comput. 5(1984)562–589.
P.E. Gill, W. Murray, M.A. Saunders and M.H. Wright, A practical anti-cycling procedure for linear and nonlinear programming, Technical Report SOL 88-4, Systems Optimization Laboratory, Stanford University, 1990.
D. Goldfarb and J. K. Reid, A practical steepest-edge simplex algorithm, Mathematical Programming 12(1977)361–371.
J.A.J. Hall and K.I.M. McKinnon, Update procedures for the parallel revised simplex method, Technical Report MSR 92-13, Department of Mathematics and Statistics, University of Edinburgh, 1992.
J.A.J. Hall and K.I.M. McKinnon, PARSMI, a parallel revised simplex algorithm incorporating minor iterations and Devex pricing, in:Applied Parallel Computing, eds. J. Waśniewski, J. Dongarra, K. Madsen and D. Olesen, Lecture Notes in Computer Science, vol. 1184, Springer, 1996, pp. 67–76.
P.M.J. Harris, Pivot selection methods of the Devex LP code, Mathematical Programming 5(1973) 1–28.
J.K. Ho and R.P. Sundarraj, On the efficacy of distributed simplex algorithms for linear programming, Computational Optimization and Applications 3(1994)349–363.
IBM, Optimization Subroutine Library, Guide and Reference, Release 2, 1993.
J. Luo, A.N.M. Hulsbosch and G.L. Reijns, An MIMD work-station for large LP problems, in: Parallel Processing and Applications, eds. E. Chiricozzi and A. D'Amico, Elsevier Science/North-Holland, 1988, pp. 159–169.
C.E. Pfefferkorn and J.A. Tomlin, Design of a linear programming system for the ILLIAC IV, Technical Report SOL 76-8, Systems Optimization Laboratory, Stanford University, 1976.
W. Shu and M. Wu, Sparse implementation of revised simplex algorithms on parallel computers, in: Proceedings of 6th SIAM Conference on Parallel Processing for Scientific Computing, 1993, pp. 501–509.
C.B. Stunkel, Linear optimization via message-based parallel processing, in: International Conference on Parallel Processing, vol. 3, August 1988, pp. 264–271.
R. Wunderling, Paralleler und objektorientierter Simplex, Technical Report TR-96-09, Konrad-Zuse-Zentrum für Informationstechnik Berlin, 1996.
Rights and permissions
About this article
Cite this article
Hall, J.A.J., McKinnon, K.I.M. ASYNPLEX, an asynchronous parallelrevised simplex algorithm. Annals of Operations Research 81, 27–50 (1998). https://doi.org/10.1023/A:1018957107705
Issue Date:
DOI: https://doi.org/10.1023/A:1018957107705