[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A computational study of a solver system for processing two-stage stochastic LPs with enhanced Benders decomposition

  • Full Length Paper
  • Published:
Mathematical Programming Computation Aims and scope Submit manuscript

Abstract

We report a computational study of two-stage SP models on a large set of benchmark problems and consider the following methods: (i) Solution of the deterministic equivalent problem by the simplex method and an interior point method, (ii) Benders decomposition (L-shaped method with aggregated cuts), (iii) Regularised decomposition of Ruszczyński (Math Program 35:309–333, 1986), (iv) Benders decomposition with regularization of the expected recourse by the level method (Lemaréchal et al. in Math Program 69:111–147, 1995), (v) Trust region (regularisation) method of Linderoth and Wright (Comput Optim Appl 24:207–250, 2003). In this study the three regularisation methods have been introduced within the computational structure of Benders decomposition. Thus second-stage infeasibility is controlled in the traditional manner, by imposing feasibility cuts. This approach allows extensions of the regularisation to feasibility issues, as in Fábián and Szőke (Comput Manag Sci 4:313–353, 2007). We report computational results for a wide range of benchmark problems from the POSTS and SLPTESTSET collections and a collection of difficult test problems compiled by us. Finally the scale-up properties and the performance profiles of the methods are presented.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Ariyawansa K.A. and Felt A.J. (2004). On a new collection of stochastic linear programming test problems. INFORMS J. Comput. 16(3): 291–299

    Article  MathSciNet  MATH  Google Scholar 

  • Beale E.M.L. (1955). On minimizing a convex function subject to linear inequalities. J. R. Stat. Soc. B 17: 173–184

    MathSciNet  MATH  Google Scholar 

  • Benders, J.F.: Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4, 238–252 (1962). Re-publised in Comput. Manag. Sci. 2, 3–19 (2005)

    Google Scholar 

  • Birge J.R. (1997). Stochastic programming computation and applications: state-of-the-art survey. INFORMS J. Comput. 9(2): 111–133

    Article  MathSciNet  MATH  Google Scholar 

  • Birge J.R., Dempster M.A.H., Gassmann H.I., Gunn E.A., King A.J. and Wallace S.W. (1987). A standard input format for multiperiod stochastic linear programs. COAL Newslett. 17: 1–19

    Google Scholar 

  • Birge J.R. and Louveaux F.V. (1988). A multicut algorithm for two-stage stochastic linear programs. Eur. J. Oper. Res. 34: 384–392

    Article  MathSciNet  MATH  Google Scholar 

  • Birge J.R. and Louveaux F.V. (1997). Introduction to Stochastic Programming. Springer, New York

    MATH  Google Scholar 

  • Colombo M. and Gondzio J. (2008). Further development of multiple centrality correctors for interior point methods. Comput. Optim. Appl. 41: 277–305

    Article  MathSciNet  MATH  Google Scholar 

  • Colombo, M., Gondzio, J., Grothey, A.: A warm-start approach for large-scale stochastic linear programs. Math. Program. (2009). doi:10.1007/s10107-009-0290-9

  • Dantzig G.B. (1955). Linear programming under uncertainty. Manag. Sci. 1: 197–206

    Article  MathSciNet  MATH  Google Scholar 

  • Dantzig, G.B., Madansky, A.: On the solution of two-stage linear programs under uncertainty. In: Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, vol. 1, pp. 165–176. University of California Press, Berkeley (1961)

  • Dantzig G.B. and Wolfe P. (1960). The decomposition principle for linear programs. Oper. Res. 8: 101–111

    Article  MATH  Google Scholar 

  • Di Domenica N., Lucas C., Mitra G. and Valente P. (2009). Scenario generation for stochastic programming and simulation: a modelling perspective. IMA J. Manag. Math. 20: 1–38

    Article  MathSciNet  MATH  Google Scholar 

  • Dolan E.D. and Moré J.J. (2002). Benchmarking optimization software with performance profiles. Math. Program. 91(2): 201–213

    Article  MathSciNet  MATH  Google Scholar 

  • Ellison, E.F.D., Mitra, G., Zverovich, V.: FortSP: a stochastic programming solver. OptiRisk Systems. http://www.optirisk-systems.com/manuals/FortspManual.pdf (2010)

  • Fábián, C.I.: Bundle-type methods for inexact data. Central Eur. J. Oper. Res. 8, 35–55 (2000). [Special issue, Csendes, T., Rapcsák, T. (eds.)]

  • Fábián C.I. and Szőke Z. (2007). Solving two-stage stochastic programming problems with level decomposition. Comput. Manag. Sci. 4: 313–353

    Article  MathSciNet  MATH  Google Scholar 

  • Fabozzi F.J., Focardi S. and Jonas C. (2007). Trends in quantitative equity management: survey results. Quant. Finance 7(2): 115–122

    Article  Google Scholar 

  • Gassmann H. (1990). MSLiP: a computer code for the multistage stochastic linear programming problem. Math. Program. 47: 407–423

    Article  MathSciNet  MATH  Google Scholar 

  • Gassmann H.I. and Wallace S.W. (1996). Solving linear programs with multiple right-hand sides: pricing and ordering schemes. Ann. Oper. Res. 64: 237–259

    Article  MathSciNet  MATH  Google Scholar 

  • Gondzio J. (1995). HOPDM (version 2.12) a fast lp solver based on a primal-dual interior point method. Eur. J. Oper. Res. 85: 221–225

    Article  MATH  Google Scholar 

  • Holmes, D.: A (PO)rtable (S)tochastic programming (T)est (S)et (POSTS). http://users.iems.northwestern.edu/~jrbirge/html/dholmes/post.html (1995)

  • Kall, P., Mayer, J.: On testing SLP codes with SLP-IOR. In: New trends in mathematical programming: homage to Steven Vajda, pp. 115–135. Kluwer, Boston (1998)

  • Kall, P., Mayer, J.: Stochastic linear programming: models, theory, and computation. Springer, International Series in Operations Research and Management Science (2005)

  • Kall P. and Wallace S.W. (1994). Stochastic Programming. Wiley, Chichester

    MATH  Google Scholar 

  • Kiwiel K.C. (1985). Methods of Descent for Nondifferentiable Optimization. Springer, Berlin

    MATH  Google Scholar 

  • König, D., Suhl, L., Koberstein, A.: Optimierung des Gasbezugs im liberalisierten Gasmarkt unter Berücksichtigung von Röhren- und Untertagespeichern. In: Sammelband zur VDI Tagung “Optimierung in der Energiewirtschaft” in Leverkusen (2007)

  • Lemaréchal, C.: Nonsmooth optimization and descent methods. Research Report 78-4, IIASA, Laxenburg, Austria (1978)

  • Lemaréchal C., Nemirovskii A. and Nesterov Y. (1995). New variants of bundle methods. Math. Program. 69: 111–147

    Article  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  • Mayer J. (1998). Stochastic Linear Programming Algorithms. Gordon and Breach Science Publishers, Amsterdam

    MATH  Google Scholar 

  • Mitra G., Di Domenica N., Birbilis G. and Valente P. (2007). Stochastic programming and scenario generation within a simulation framework: An information perspective. Decis. Support Syst. 42: 2197–2218

    Article  Google Scholar 

  • Nemirovski A. (2005). Lectures in Modern Convex Optimization. ISYE, Georgia Institute of Technology

    Google Scholar 

  • Oliveira W., Sagastizábal C. and Scheimberg S. (2011). Inexact bundle methods for two-stage stochastic programming. SIAM J. Optim. 21: 517–544

    Article  MathSciNet  MATH  Google Scholar 

  • Prékopa A. (1995). Stochastic Programming. Kluwer, Dordrecht

    Google Scholar 

  • Rockafellar R.T. (1976). Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14: 877–898

    Article  MathSciNet  MATH  Google Scholar 

  • Ruszczyński A. (1986). A regularized decomposition method for minimizing a sum of polyhedral functions. Math. Program. 35: 309–333

    Article  MATH  Google Scholar 

  • Ruszczyński A. (2003). Decomposition methods. In: Ruszczyński, A. and Shapiro, A. (eds) Stochastic Programming. Handbooks in Operations Research and Management Science, vol. 10, pp 141–211. Elsevier, Amsterdam

    Google Scholar 

  • Ruszczyński A. (2006). Nonlinear Optimization. Princeton University Press, Princeton

    MATH  Google Scholar 

  • Ruszczyński, A., Shapiro, A. : Stochastic programming models. In: Ruszczyński, A., Shapiro, A. (eds.) Stochastic Programming. Handbooks in Operations Research and Management Science, vol. 10, pp. 1–64. Elsevier, Amsterdam (2003)

  • Ruszczyński A. and Świȩtanowski A. (1997). Accelerating the regularized decomposition method for two-stage stochastic linear problems. Eur. J. Oper. Res. 101: 328–342

    Article  MATH  Google Scholar 

  • Valente C., Mitra G., Sadki M. and Fourer R. (2009). Extending algebraic modelling languages for stochastic programming. INFORMS J. Comput. 21(1): 107–122

    Article  MathSciNet  MATH  Google Scholar 

  • Valente, P., Mitra, G., Poojari, C., Ellison, E.F., Di Domenica, N., Mendi, M., Valente, C.: SAMPL/SPInE user manual. OptiRisk Systems. http://www.optirisk-systems.com/manuals/SpineAmplManual.pdf (2008)

  • Van Slyke R. and Wets R.J.B. (1969). L-shaped linear programs with applications to optimal control and stochastic programming. SIAM J. Appl. Math. 17: 638–663

    Article  MathSciNet  MATH  Google Scholar 

  • Wallace, S.W., Ziemba, W.T. (eds.): Applications of Stochastic Programming. Society for Industrial and Applied Mathematic (2005)

  • Wets R.J.B. (1974). Stochastic programs with fixed recourse: the equivalent deterministic program. SIAM Rev. 16: 309–339

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. OptiRisk Systems, OptiRisk R&D House, One Oxford Road, Uxbridge, Middlesex, UB9 4DA, UK

    Victor Zverovich, Eldon F. D. Ellison & Gautam Mitra

  2. The Centre for the Analysis of Risk and Optimisation Modelling Applications (CARISMA), School of Information Systems, Computing and Mathematics, Brunel University, London, UK

    Eldon F. D. Ellison & Gautam Mitra

  3. Institute of Informatics, Kecskemét College, 10 Izsáki út, Kecskemét, 6000, Hungary

    Csaba I. Fábián

  4. Department of OR, Loránd Eötvös University, Budapest, Hungary

    Csaba I. Fábián

Authors
  1. Victor Zverovich
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Csaba I. Fábián
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Eldon F. D. Ellison
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Gautam Mitra
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Victor Zverovich.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Zverovich, V., Fábián, C.I., Ellison, E.F.D. et al. A computational study of a solver system for processing two-stage stochastic LPs with enhanced Benders decomposition. Math. Prog. Comp. 4, 211–238 (2012). https://doi.org/10.1007/s12532-012-0038-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12532-012-0038-z

Mathematics Subject Classification

Search

Navigation