Abstract
This paper presents a parallelization of the simplex method for linear programming. Current implementations of the simplex method on sequential computers are based on a triangular factorization of the inverse of the current basis. An alternative decomposition designed for parallel computation, called the quadrant interlocking factorization, has previously been proposed for solving linear systems of equations. This research presents the theoretical justification and algorithms required to implement this new factorization in a simplex-based linear programming system.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R.H. Bartels, A Stabilization of the Simplex Method,Numer. Math. 16 (1971) 414–434.
S.S. Chen, J.J. Dongarra andC.C. Hsiung, Multiprocessing Linear Algebra Algorithms on the CRAY X-MP-2: Experiences with Small Granularity,J. Parallel and Distributed Computing 1 (1984) 22–31.
J.J. Dongarra andD.C. Sorensen, A Parallel Linear Algebra Library for the Denelcor HEP, Argonne Nat. Lab., Argonne, IL, Rep. ANL/MCS-TM-33 (1984).
——————, andT. Hewitt, Implementing Dense Linear Algebra Algorithms Using Multitasking on the CRAY X-MP-4,SIAM J. Sci. Stat. Comput. 7 (1986) 347–350.
D.J. Evans andM. Hatzopoulos, A Parallel Linear System Solver,Intern. J. Computer Math. 7 (1979) 227–238.
——————, andA. Hadjidimos, A Modification of the Quadrant Interlocking Factorisation Parallel Method,Intern. J. Computer Math. 8 (1980) 149–166.
——————, Parallel Numerical Algorithms for Linear Systems, in:Parallel Processing Systems D.J. Evans, ed., (Cambridge Univ. Press, Cambridge (1982) 357–384.)
M. Feilmeier, Parallel Numerical Algorithms, in:Parallel Processing Systems D.J. Evans, ed., (Cambridge University Press, Cambridge (1982) 285–338.)
J.J.H. Forrest andJ.A. Tomlin, Updated Triangular Factors of the Basis to Maintain Sparsity in the Product Form Simplex Method,Math. Program. 2 (1972) 263–278.
R.L. Hellier, DAP Implementation of the WZ Algorithm,Comp. Phys. Comm. 26 (1982) 321–323.
H.M. Markowitz, The Elimination Form of the Inverse and its Application to Linear Programming,Management Sci. 3 (1957) 255–269.
A. Osterhaug,Guide to Parallel Programming, Sequent Computer Systems, Inc., Beaverton, Oregon (1986).
J.K. Reid, A Sparsity Exploiting Variant of the Bartels-Golub Decomposition for Linear Programming Bases,Math. Program. 24 (1982) 55–69.
M.A. Saunders, A Fast, Stable Implementation of the Simplex Method Using Bartels-Golub Updating, in:Sparse Matrix Computations, ed.,J.R. Bunch andD.J. Rose (Academic press, New York, N.Y. (1976) 213–226.)
J. Shanehchi andD.J. Evans, Further Analysis of the Quadrant Interlocking Factorization (Q.I.F.) Method,Intern. J. Computer Math. 11 (1982) 49–72.
H.A. Zaki,A Parallelization of the Simplex Method Using the Quadrant Interlocking Factorization, unpublished dissertation, Department of Operations Research and Engineering Management, Southern Methodist University, Dallas, Texas (1986).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Helgason, R.V., Kennington, J.L. & Zaki, H.A. A parallelization of the simplex method. Ann Oper Res 14, 17–40 (1988). https://doi.org/10.1007/BF02186472
Issue Date:
DOI: https://doi.org/10.1007/BF02186472