Skip to main content
SpringerLink
Log in

Towards a practical parallelisation of the simplex method

  • Original Paper
  • Published:
Computational Management Science Aims and scope Submit manuscript

Abstract

The simplex method is frequently the most efficient method of solving linear programming (LP) problems. This paper reviews previous attempts to parallelise the simplex method in relation to efficient serial simplex techniques and the nature of practical LP problems. For the major challenge of solving general large sparse LP problems, there has been no parallelisation of the simplex method that offers significantly improved performance over a good serial implementation. However, there has been some success in developing parallel solvers for LPs that are dense or have particular structural properties. As an outcome of the review, this paper identifies scope for future work towards the goal of developing parallel implementations of the simplex method that are of practical value.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Agrawal A, Blelloch GE, Krawitz RL, Phillips CA (1989) Four vector–matrix primitives. In: ACM symposium on parallel algorithms and architectures, pp 292–302

  • Amdahl GM (1967) Validity of the single-processor approach to achieving large scale computing capabilities. In: AFIPS conference proceedings, vol 30. AFIPS Press, Reston, pp 483–485

  • Amestoy PR, Duff IS, L’Excellent J-Y (2000) Multifrontal parallel distributed symmetric and unsymmetric solvers. Comput Methods Appl Mech Eng 184: 501–520

    Article  Google Scholar 

  • Amestoy PR, Duff IS, Koster J, L’Excellent J-Y (2001) A fully asynchronous multifrontal solver using distributed dynamic scheduling. SIAM J Matrix Anal Appl 23(1): 15–41

    Article  Google Scholar 

  • Amestoy PR, Guermouche A, L’Excellent J-Y, Pralet S (2006) Hybrid scheduling for the parallel solution of linear systems. Parallel Comput 32(2): 136–156

    Article  Google Scholar 

  • Amestoy P, Li XS, Ng EG (2007a) Diagonal Markowitz scheme with local symmetrization. SIAM J Matrix Anal Appl 29(1): 228–244

    Article  Google Scholar 

  • Amestoy P, Pralet S, Li XS (2007b) Unsymmetric orderings using a constrained Markowitz scheme. SIAM J Matrix Anal Appl 29(1): 302–327

    Article  Google Scholar 

  • Aykanat C, Pinar A, Çatalyürek ÜV (2004) Permuting sparse rectangular matrices into block-diagonal form. SIAM J Sci Comput 25(6): 1860–1879

    Article  Google Scholar 

  • Babaev DA, Mardanov SS (1991) A parallel algorithm for solving linear programming problems. Zh Vychislitel’noi Matematiki Matematicheskoi Fiziki 31(1): 86–95

    Google Scholar 

  • Badr E-S, Moussa M, Papparrizos K, Samaras N, Sifaleras A (2006) Some computational results on MPI parallel implementations of dense simplex method. Trans Eng Comput Technol 17: 228–231

    Google Scholar 

  • Barr RS, Hickman BL (1994) Parallel simplex for large pure network problems: computational testing and sources of speedup. Oper Res 42(1): 65–80

    Article  Google Scholar 

  • Beasley JE (1990) Linear programming on Cray supercomputers. J Oper Res Soc 41(2): 133–139

    Article  Google Scholar 

  • Benders JF (1962) Partitioning procedures for solving mixed-variables programming problems. Numer Math 4: 238–252

    Article  Google Scholar 

  • Bixby RE (2002) Solving real-world linear programs: a decade and more of progress. Oper Res 50(1): 3–15

    Article  Google Scholar 

  • Bixby RE, Martin A (2000) Parallelizing the dual simplex method. INFORMS J Comput 12: 45–56

    Article  Google Scholar 

  • Bixby RE, Fenelon M, Gu Z, Rothberg E, Wunderling R (2000) MIP: theory and practice closing the gap. In: Powell MJD, Scholtes S (eds) System modelling and optimization: methods, theory and applications. Kluwer, The Netherlands, pp 19–49

    Google Scholar 

  • Bodurog̃lu İİ (1997) Scalable massively parallel simplex algorithms for block-structured linear programs. Ph.D. thesis, GSAS, Columbia University, New York

  • Boffey TB, Hay R (1989) Implementing parallel simplex algorithms. In: CONPAR 88. Cambridge, UK, Cambridge University Press, pp 169–176

  • Carolan WJ, Hill JE, Kennington JL, Niemi S, Wichmann SJ (1990) An empirical evaluation of the KORBX algorithms for military airlift applications. Oper Res 38(2): 240–248

    Article  Google Scholar 

  • Chang MD, Engquist M, Finkel R, Meyer RR (1988) A parallel algorithm for generalized networks. Ann Oper Res 14: 125–145

    Article  Google Scholar 

  • Crowder H, Hattingh JM (1975) Partially normalized pivot selection in linear programming. Math Program Study 4: 12–25

    Google Scholar 

  • Cvetanovic Z, Freedman EG, Nofsinger C (1991) Efficient decomposition and performance of parallel PDE, FFT, Monte-Carlo simulations, simplex, and sparse solvers. J Supercomput 5: 19–38

    Article  Google Scholar 

  • Dantzig GB (1960) The decomposition principle for linear programs. Oper Res 8: 101–111

    Article  Google Scholar 

  • Dantzig GB, Orchard-Hays W (1954) The product form for the inverse in the simplex method. Math Comput 8: 64–67

    Article  Google Scholar 

  • Demmel JW, Eisenstat SC, Gilbert JR, Li XS, Liu JWH (1999) A supernodal approach to sparse partial pivoting. SIAM J Matrix Anal Appl 20(3): 720–755

    Article  Google Scholar 

  • Dempster MAH, Thompson RT (1998) Parallelization and aggregation of nested Benders decomposition. Ann Oper Res 81: 163–187

    Article  Google Scholar 

  • Eckstein J, Bodurog̃lu İİ, Polymenakos L, Goldfarb D (1995) Data-parallel implementations of dense simplex methods on the connection machine CM-2. ORSA J Comput 7(4): 402–416

    Google Scholar 

  • Evans DJ, Hatzopoulos M (1979) A parallel linear system solver. Int J Comput Math 7: 227–238

    Article  Google Scholar 

  • Ferris MC, Horn JD (1998) Partitioning mathematical programs for parallel solution. Math Program 80: 35–61

    Google Scholar 

  • Finkel RA (1987) Large-grain parallelism: three case studies. In: Jamieson LH, Gannon D, Douglas RJ (eds) The characteristics of parallel algorithms. MIT Press, Cambridge, pp 21–63

    Google Scholar 

  • Forrest JJ, Goldfarb D (1992) Steepest-edge simplex algorithms for linear programming. Math Program 57: 341–374

    Article  Google Scholar 

  • Forrest JJH, Tomlin JA (1990) Vector processing in the simplex and interior methods for linear programming. Ann Oper Res 22: 71–100

    Article  Google Scholar 

  • Gay DM (1985) Electronic mail distribution of linear programming test problems. Math Program Soc COAL Newsl 13: 10–12

    Google Scholar 

  • Gill PE, Murray W, Saunders MA, Wright MH (1989) A practical anti-cycling procedure for linearly constrained optimization. Math Program 45: 437–474

    Article  Google Scholar 

  • Gnanendran SK, Ho JK (1993) Load balancing in the parallel optimization of block-angular linear programs. Math Program 62: 41–67

    Article  Google Scholar 

  • Goldfarb D, Reid JK (1977) A practical steepest-edge simplex algorithm. Math Program 12: 361–371

    Article  Google Scholar 

  • Hall JAJ (2005) SYNPLEX: a task-parallel scheme for the revised simplex method. In: Contributed talk at the second international workshop on combinatorial scientific computing (CSC05), June 2005

  • Hall JAJ (2007) Parallel basis matrix triangularisation for hyper-sparse LP problems. In: Contributed talk the IMA conference on numerical linear algebra and optimisation, September 2007

  • Hall JAJ, McKinnon KIM (1992) Update procedures for the parallel revised simplex method. Technical report MSR 92-13, Department of Mathematics and Statistics, University of Edinburgh

  • Hall JAJ, McKinnon KIM (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, vol 1184. Lecture notes in computer science. Springer, Berlin, pp 67–76

    Google Scholar 

  • Hall JAJ, McKinnon KIM (1998) ASYNPLEX: an asynchronous parallel revised simplex method algorithm. Ann Oper Res 81: 27–49

    Article  Google Scholar 

  • Hall JAJ, McKinnon KIM (1999) Exploiting hyper-sparsity in the revised simplex method. Technical report MS99-014. Department of Mathematics and Statistics, University of Edinburgh

  • Hall JAJ, McKinnon KIM (2005) Hyper-sparsity in the revised simplex method and how to exploit it. Comput Optim Appl 32(3): 259–283

    Article  Google Scholar 

  • Harris PMJ (1973) Pivot selection methods of the Devex LP code. Math Program 5: 1–28

    Article  Google Scholar 

  • Helgason RV, Kennington LJ, Zaki HA (1988) A parallelisation of the simplex method. Ann Oper Res 14: 17–40

    Article  Google Scholar 

  • Hiller RS, Eckstein J (1993) Stochastic dedication: designing fixed income portfolios using massively parallel Benders decomposition. Manage Sci 39(11): 1422–1438

    Article  Google Scholar 

  • Ho JK, Lee TC, Sundarraj RP (1988) Decomposition of linear programs using parallel computation. Math Program 42: 391–405

    Article  Google Scholar 

  • Ho JK, Sundarraj RP (1994) On the efficacy of distributed simplex algorithms for linear programming. Comput Optim Appl 3(4): 349–363

    Article  Google Scholar 

  • Kaul RN (1965) An extension of generalized upper bounding techniques for linear programming. Technical Report ORC 65-27. In: Center OR, Berkley UC, San Fransisco, CA

  • Klabjan D, Johnson EL, Nemhauser GL (2000) A parallel primal-dual simplex algorithm. Oper Res Lett 27: 47–55

    Article  Google Scholar 

  • Kumar V, Grama A, Gupta A, Karypis G (2003) Introduction to parallel computing: design and analysis of algorithms, 2nd edn. Addison–Wesley, New York

    Google Scholar 

  • Lentini M, Reinoza A, Teruel A, Guillen A (1995) SIMPAR: a parallel sparse simplex. Comput Appl Math 14(1): 49–58

    Google Scholar 

  • Li XS, Demmel JW (2003) SuperLU_DIST: a scalable distributed-memory sparse direct solver for unsymmetric linear systems. ACM Trans Math Softw 29(2): 110–140

    Article  Google Scholar 

  • Luo J, Reijns GL (1992) Linear programming on transputers. In: van Leeuwen J (eds) Algorithms, software, architecture IFIP. transactions A (computer science and technology). Elsevier, Amsterdam, pp 525–534

    Google Scholar 

  • Luo J, Reijns GL, Bruggeman F, Lindfield GR (1991) A survey of parallel algorithms for linear programming. In: Deprettere EF, van der Veen A-J (eds) Algorithms and parallel VLSI architectures, vol B. Elsevier, Amsterdam, pp 485–490

    Google Scholar 

  • Markowitz H (1957) The elimination form of the inverse and its application to linear programming. Manage Sci 3: 255–296

    Article  Google Scholar 

  • Maros I, Mitra G (2000) Investigating the sparse simplex algorithm on a distributed memory multiprocessor. Parallel Comput 26: 151–170

    Article  Google Scholar 

  • McKinnon KIM, Plab F (1997a) A modified Markowitz criterion to increase parallelism in inverse factors of sparse matrices. Technical report, Department of Mathematics and Statistics, University of Edinburgh

  • McKinnon KIM, Plab F (1997b) An upper bound on parallelism in the forward transformation within the revised simplex method. Technical report, Department of Mathematics and Statistics, University of Edinburgh

  • Medhi D (1990) Parallel bundle-based decomposition algorithm for large-scale structured mathematical programming problems. Ann Oper Res 22: 101–127

    Article  Google Scholar 

  • Mittelmann HD (2008) Benchmarks for optimization software. http://plato.asu.edu/bench.html. Accessed February 2008

  • Nielsen SN, Zenios SA (1997) Scalable Benders decomposition for stochastic linear programming. Parallel Comput 23: 1069–1088

    Article  Google Scholar 

  • Orchard-Hays W (1968) Advanced linear programming computing techniques. McGraw-Hill, New York

    Google Scholar 

  • Peters J (1990) The network simplex method on a multiprocessor. Networks 20: 845–859

    Article  Google Scholar 

  • Pfefferkorn CE, Tomlin JA (1976) Design of a linear programming system for the ILLIAC IV. Technical report SOL 76-8. Systems Optimization Laboratory, Stanford University

  • Pinar A, Aykanat C (1996) An effective model to decompose linear programs for parallel solution. In: Waśniewski J, Dongarra J, Madsen K, Olesen D (eds) Applied parallel computing. Lecture notes in computer science, vol 1184. Springer, Heidelberg, pp 592–601

    Google Scholar 

  • Rosen JB, Maier RS (1990) Parallel solution of large-scale, block-angular linear programs. Ann Oper Res 22: 23–41

    Article  Google Scholar 

  • Shu W (1995) Parallel implementation of a sparse simplex algorithm on MIMD distributed memory computers. J Parallel Distrib Comput 31(1): 25–40

    Article  Google Scholar 

  • Stunkel CB (1988) Linear optimization via message-based parallel processing. In: International conference on parallel processing, vol III, August 1988, pp 264–271

  • Suhl UH, Suhl LM (1990) Computing sparse LU factorizations for large-scale linear programming bases. ORSA J Comput 2(4): 325–335

    Google Scholar 

  • Thomadakis ME, Liu J-C (1996) An efficient steepest-edge simplex algorithm for SIMD computers. In: International conference on supercomputing, pp 286–293

  • Tomlin JA (1972) Pivoting for size and sparsity in linear programming inversion routines. J Inst Maths Applics 10: 289–295

    Article  Google Scholar 

  • Wunderling R (1996a) Parallelizing the simplex algorithm. ILAY workshop on linear algebra in optimzation, Albi

  • Wunderling R (1996b) Paralleler und objektorientierter simplex. Technical report TR-96-09, Konrad-Zuse-Zentrum für Informationstechnik Berlin

  • Yarmish G (2001) A distributed implementation of the simplex method. Ph.D. thesis, Polytechnic University, Brooklyn, NY, March 2001

  • Zenios SA (1989) Parallel numerical optimization: current status and annotated bibliography. ORSA J Comput 1(1)(Winter): 20–43

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Mathematics, University of Edinburgh, JCMB, King’s Buildings, Edinburgh, EH9 3JZ, UK

    J. A. J. Hall

Authors
  1. J. A. J. Hall
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to J. A. J. Hall.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hall, J.A.J. Towards a practical parallelisation of the simplex method. Comput Manag Sci 7, 139–170 (2010). https://doi.org/10.1007/s10287-008-0080-5

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10287-008-0080-5

Keywords

Mathematics Subject Classification (2000)

Search

Navigation