Skip to main content
SpringerLink
Log in

Parallel distributed-memory simplex for large-scale stochastic LP problems

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

We present a parallelization of the revised simplex method for large extensive forms of two-stage stochastic linear programming (LP) problems. These problems have been considered too large to solve with the simplex method; instead, decomposition approaches based on Benders decomposition or, more recently, interior-point methods are generally used. However, these approaches do not provide optimal basic solutions, which allow for efficient hot-starts (e.g., in a branch-and-bound context) and can provide important sensitivity information. Our approach exploits the dual block-angular structure of these problems inside the linear algebra of the revised simplex method in a manner suitable for high-performance distributed-memory clusters or supercomputers. While this paper focuses on stochastic LPs, the work is applicable to all problems with a dual block-angular structure. Our implementation is competitive in serial with highly efficient sparsity-exploiting simplex codes and achieves significant relative speed-ups when run in parallel. Additionally, very large problems with hundreds of millions of variables have been successfully solved to optimality. This is the largest-scale parallel sparsity-exploiting revised simplex implementation that has been developed to date and the first truly distributed solver. It is built on novel analysis of the linear algebra for dual block-angular LP problems when solved by using the revised simplex method and a novel parallel scheme for applying product-form updates.

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

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Notes

  1. https://projects.coin-or.org/CoinUtils.

  2. https://projects.coin-or.org/Clp.

  3. http://pages.cs.wisc.edu/~swright/stochastic/sampling.

References

  1. Amdahl, G.M.: Validity of the single processor approach to achieving large scale computing capabilities. In: Proceedings of the April 18–20, 1967, Spring Joint Computer Conference, AFIPS ’67 (Spring), pp. 483–485. ACM, New York (1967)

    Chapter  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  3. Bennett, J.M.: An approach to some structured linear programming problems. Oper. Res. 14(4), 636–645 (1966)

    Article  MATH  Google Scholar 

  4. Birge, J., Louveaux, F.: Introduction to Stochastic Programming, 2nd edn. Springer Series in Operations Research and Financial Engineering. Springer, New York (2011)

    Book  MATH  Google Scholar 

  5. Bisschop, J., Meeraus, A.: Matrix augmentation and partitioning in the updating of the basis inverse. Math. Program. 13, 241–254 (1977)

    Article  MathSciNet  MATH  Google Scholar 

  6. Dantzig, G.B., Orchard-Hays, W.: The product form for the inverse in the simplex method. Math. Tables Other Aids Comput. 8(46), 64–67 (1954)

    Article  MathSciNet  MATH  Google Scholar 

  7. Davis, T.: Direct Methods for Sparse Linear Systems. Fundamentals of Algorithms. Society for Industrial and Applied Mathematics, Philadelphia (2006)

    Book  Google Scholar 

  8. Duff, I.S., Scott, J.A.: A parallel direct solver for large sparse highly unsymmetric linear systems. ACM Trans. Math. Softw. 30, 95–117 (2004)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  10. Forrest, J.J.H., Tomlin, J.A.: Updated triangular factors of the basis to maintain sparsity in the product form simplex method. Math. Program. 2, 263–278 (1972)

    Article  MathSciNet  MATH  Google Scholar 

  11. Gilbert, J.R., Peierls, T.: Sparse partial pivoting in time proportional to arithmetic operations. SIAM J. Sci. Stat. Comput. 9, 862–874 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  12. Gill, P.E., Murray, W., Saunders, M.A., Wright, M.H.: A practical anti-cycling procedure for linearly constrained optimization. Math. Program. 45, 437–474 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  13. Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996)

    MATH  Google Scholar 

  14. Gondzio, J., Grothey, A.: Exploiting structure in parallel implementation of interior point methods for optimization. Comput. Manag. Sci. 6, 135–160 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  15. Grama, A., Karypis, G., Kumar, V., Gupta, A.: Introduction to Parallel Computing, 2nd edn. Addison-Wesley, Reading (2003)

    Google Scholar 

  16. Gropp, W., Thakur, R., Lusk, E.: Using MPI-2: Advanced Features of the Message Passing Interface, 2nd edn. MIT Press, Cambridge (1999)

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  18. Hall, J.A.J., Smith, E.: A high performance primal revised simplex solver for row-linked block angular linear programming problems. Tech. Rep. ERGO-12-003, School of Mathematics, University of Edinburgh (2012)

  19. Harris, P.M.J.: Pivot selection methods of the DEVEX LP code. Math. Program. 5, 1–28 (1973)

    Article  MATH  Google Scholar 

  20. Kall, P.: Computational methods for solving two-stage stochastic linear programming problems. Z. Angew. Math. Phys. 30, 261–271 (1979)

    Article  MathSciNet  MATH  Google Scholar 

  21. Koberstein, A.: The dual simplex method, techniques for a fast and stable implementation. Ph.D. thesis, Universität Paderborn, Paderborn, Germany (2005)

  22. Koberstein, A.: Progress in the dual simplex algorithm for solving large scale LP problems: techniques for a fast and stable implementation. Comput. Optim. Appl. 41, 185–204 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  23. Lasdon, L.S.: Optimization Theory for Large Systems. Macmillan, New York (1970)

    MATH  Google Scholar 

  24. Linderoth, J., Wright, S.: Decomposition algorithms for stochastic programming on a computational grid. Comput. Optim. Appl. 24, 207–250 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  25. Lubin, M., Petra, C.G., Anitescu, M., Zavala, V.: Scalable stochastic optimization of complex energy systems. In: Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, SC ’11, pp. 64:1–64:64. ACM, New York (2011)

    Google Scholar 

  26. Markowitz, H.M.: The elimination form of the inverse and its application to linear programming. Manag. Sci. 3(3), 255–269 (1957)

    Article  MathSciNet  MATH  Google Scholar 

  27. Maros, I.: Computational Techniques of the Simplex Method. Kluwer Academic, Norwell (2003)

    Book  MATH  Google Scholar 

  28. Stern, J., Vavasis, S.: Active set methods for problems in column block angular form. Comput. Appl. Math. 12, 199–226 (1993)

    MathSciNet  MATH  Google Scholar 

  29. Strazicky, B.: Some results concerning an algorithm for the discrete recourse problem. In: Stochastic Programming (Proc. Internat. Conf., Univ. Oxford, Oxford, 1974), pp. 263–274. Academic Press, London (1980)

    Google Scholar 

  30. Suhl, L.M., Suhl, U.H.: A fast LU update for linear programming. Ann. Oper. Res. 43, 33–47 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  31. Suhl, U.H., Suhl, L.M.: Computing sparse LU factorizations for large-scale linear programming bases. ORSA J. Comput. 2(4), 325 (1990)

    Article  MATH  Google Scholar 

  32. Vladimirou, H., Zenios, S.: Scalable parallel computations for large-scale stochastic programming. Ann. Oper. Res. 90, 87–129 (1999)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

We acknowledge John Forrest and all other contributors for the open-source CoinUtils library which is used throughout the implementation. This work was supported by the U.S. Department of Energy under Contract DE-AC02-06CH11357. This research used resources of the Laboratory Computing Resource Center and the Argonne Leadership Computing Facility at Argonne National Laboratory, which is supported by the Office of Science of the U.S. Department of Energy under contract DE-AC02-06CH11357. Computing time on Intrepid was granted by a 2012 DOE INCITE Award “Optimization of Complex Energy Systems Under Uncertainty,” PI Mihai Anitescu.

Author information

Authors and Affiliations

  1. Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL, 60439-4844, USA

    Miles Lubin, Cosmin G. Petra & Mihai Anitescu

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

    J. A. Julian Hall

Authors
  1. Miles Lubin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J. A. Julian Hall
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Cosmin G. Petra
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Mihai Anitescu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Miles Lubin.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Lubin, M., Hall, J.A.J., Petra, C.G. et al. Parallel distributed-memory simplex for large-scale stochastic LP problems. Comput Optim Appl 55, 571–596 (2013). https://doi.org/10.1007/s10589-013-9542-y

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-013-9542-y

Keywords

Search

Navigation