Abstract
When solving linear programming problems using the revised simplex method, two common variants are the incorporation of minor iterations of the standard simplex method applied to a small subset of the variables and the use of Devex pricing. Although the extra work per iteration which is required when updating Devex weights removes the advantage of using minor iterations in a serial computation, the extra work parallelises readily. An asynchronous parallel algorithm PARSMI is presented in which computational components of the revised simplex method with Devex pricing are either overlapped or parallelism is exploited within them. Minor iterations are used to achieve good load balance and tackle problems caused by limited candidate persistence. Initial computational results for an six-processor implementation on a Cray T3D indicate that the algorithm has a significantly higher iteration rate than an efficient sequential implementation.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
R. Barriuso and A. Knies. SEMEM User's guide for Fortran. Cray Research inc.
R. E. Bixby and A. Martin. Parallelizing the dual simplex method. Technical Report SC-95-45, Konrad-Zuse-Zentrum für Informationstechnik Berlin, 1995.
D. M. Gay. Electronic mail distribution of linear programming test problems. Mathematical Programming Society COAL Newsletter, 13:10–12, 1985.
A. Geist, A. Beguelin, J. Dongarra, W. Jiang, R. Manchek, and V. Sunderam. PVM: Parallel Virtual Machine — A User's Guide and Tutorial for Networked Parallel Computing. MIT Press.
J. A. J. Hall and K. I. M. McKinnon. An asynchronous parallel revised simplex method algorithm. Technical Report MS 95-50, Department of Mathematics and Statistics, University of Edinburgh, 1995.
P. M. J. Harris. Pivot selection methods of the Devex LP code. Math. Prog., 5:1–28, 1973.
W. Shu and M. Wu. Sparse implementation of revised simplex algorithms on parallel computers. In Proceedings of 6 th SIAM Conference on Parallel Processing for Scientific Computing, pages 501–509, 1993.
R. Wunderling. Parallelizing the simplex algorithm. ILAY Workshop on Linear Algebra in Optimzation, Albi, April 1996.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hall, J.A.J., McKinnon, K.I.M. (1996). PARSMI, a parallel revised simplex algorithm incorporating minor iterations and Devex pricing. In: Waśniewski, J., Dongarra, J., Madsen, K., Olesen, D. (eds) Applied Parallel Computing Industrial Computation and Optimization. PARA 1996. Lecture Notes in Computer Science, vol 1184. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-62095-8_38
Download citation
DOI: https://doi.org/10.1007/3-540-62095-8_38
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-62095-2
Online ISBN: 978-3-540-49643-4
eBook Packages: Springer Book Archive