Skip to main content
SpringerLink
Log in

On the formulation of stochastic linear programs using algebraic modelling languages

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

This paper considers extensions to algebraic modelling languages to support formulation, instantiation and solver integration for stochastic linear programs (SLPs). We present a taxonomy of SLP problem types and analyze formulation requirements including distribution handling by class of problem. We demonstrate suggested formulations for most problem classes, show solver input in the S-MPS standard, and propose consistency checks for constraints involving stochastic data items. Some unresolved difficulties are identified.

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

  1. E.M.L. Beale, On minimizing a convex function subject to linear inequalities, Journal of the Royal Statistical Society, Series B 17, 1955, 173–184.

    Google Scholar 

  2. B. Bereanu, The distribution problem in stochastic linear programming, Operations Research Verfahren 8, 1970, 22–35.

    Google Scholar 

  3. J.R. Birge, Decomposition and partitioning methods for multistage stochastic programs, Operations Research 33, 1985, 989–1007.

    Google Scholar 

  4. J.R. Birge, M.A.H. Dempster, H.I. Gassmann, E.A. Gunn, A.J. King and S.W. Wallace, A standard input format for multiperiod stochastic linear programs, Committee on Algorithms Newsletter 17, 1988, 1–19.

    Google Scholar 

  5. J.R. Birge and D. Holmes, Efficient solution of two-stage stochastic linear programs using interior point methods, Computational Optimization and Applications 1, 1992, 245–276.

    Article  Google Scholar 

  6. J. Bisschop and R. Entriken,AIMMS: The Modelling System, Paragon Decision Technology, 2001 DG Haarlem, The Netherlands, 1993.

    Google Scholar 

  7. A. Brooke, D. Kendrick and A. Meeraus,GAMS: A User Guide, The Scientific Press, Redwood City, CA, 1988.

    Google Scholar 

  8. D.R. Cariño, T. Kent, D.H. Myers, C. Stacy, M. Sylvanus, A.L. Turner, K. Watanabe and W.T. Ziemba, The Russell—Yasuda Kasai model: An asset/liability model for a Japanese insurance company using multistage stochastic programming, Interfaces 24, Jan.-Feb. 1994, 29–49.

    Google Scholar 

  9. A. Charnes and W.W. Cooper,Management Models and Industrial Applications of Linear Programming, Vol. 1, Wiley, New York, 1961.

    Google Scholar 

  10. K. Cunningham and L. Schrage, The LINGO modelling language, Technical Report, University of Chicago, Chicago, IL, 1989.

    Google Scholar 

  11. J. Czyzyk, R. Fourer and S. Mehrotra, A study of the augmented system and column-splitting approaches for solving two-stage stochastic linear programs by interior-point methods, Technical Report 93-05, Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL, 1993.

    Google Scholar 

  12. G.B. Dantzig, Linear programming under uncertainty, Management Science 1, 1955, 197–206.

    Google Scholar 

  13. M.A.H. Dempster and A.M. Ireland, A financial expert decision support system, inMathematical Models for Decision Support, G. Mitra, ed., NATO ASI Series F 48, Springer, Berlin, 1988, pp. 415–440.

    Google Scholar 

  14. Yu. Ermoliev, Stochastic quasigradient methods, inNumerical Techniques for Stochastic Optimization, Yu. Ermoliev and R.J-B. Wets, eds., Springer Series in Computational Mathematics, Vol. 10, Springer, Berlin, 1988, pp. 141–185.

    Google Scholar 

  15. R. Fourer, D.M. Gay and B.W. Kernighan,AMPL: A Modeling Language for Mathematical Programming, The Scientific Press, South San Francisco, CA, 1993.

    Google Scholar 

  16. H.I. Gassmann, MSLiP: A computer code for the multistage stochastic linear programming problem, Mathematical Programming 47, 1990, 407–423.

    Article  Google Scholar 

  17. H.I. Gassmann and A.M. Ireland, Scenario formulation in an algebraic modelling language, Annals of Operations Research 59, 1995, 45–75.

    Article  MathSciNet  Google Scholar 

  18. A. Gaivoronski, Implementation of stochastic quasigradient methods, inNumerical Techniques for Stochastic Optimization, Yu. Ermoliev and R.J-B Wets, eds., Springer Series in Computational Mathematics, Vol. 10, Springer, Berlin, 1988, pp. 313–351.

    Google Scholar 

  19. H.J. Greenberg,A Computer-Assisted Analysis System for Mathematical Programming Models and Solutions, Kluwer Academic, Boston, MA, 1993.

    Google Scholar 

  20. H.J. Greenberg,Modeling by Object-Driven Linear Elemental Relations: A User's Guide for MODLER, Kluwer Academic, Boston, MA, 1993.

    Google Scholar 

  21. H.J. Greenberg and F.H. Murphy, A comparison of mathematical programming modeling systems. Annals of Operations Research 38, 1992, 239–280.

    Google Scholar 

  22. J.L. Higle and S. Sen, Stochastic decomposition: An algorithm for two-stage linear programs with recourse, Mathematics of Operations Research 16, 1991, 650–669.

    Google Scholar 

  23. J.L. Higle and S. Sen, Guidelines for a computer implementation of stochastic decomposition algorithms, Technical Report, Department of Systems and Industrial Engineering, University of Arizona, Tucson, AZ, 1991.

    Google Scholar 

  24. T. Hürlimann, Reference Manual for the LPL Modeling Language (Version 3.1), Institute for Automation and Operations Research, University of Fribourg, CH-1700 Fribourg, Switzerland, 1989.

    Google Scholar 

  25. International Business Machines, Inc.,Mathematical Programming Subsystem — Extended (MPSX) and Generalized Upper Bounding (GUB) Program Description, document number SH20-0968-1, 1972.

  26. P. Kall,Stochastic Linear Programming, Springer, Berlin, 1976.

    Google Scholar 

  27. P. Kall and J. Mayer, SLP-IOR: A model management system for stochastic linear programming — system design, inOptimization-Based Computer-Aided Modelling and Design, A.J.M. Beulens and H.-J. Sebastian, eds., Springer, 1992, pp. 139–157.

  28. P. Kall and J. Mayer, A model management system for stochastic linear programming, inSystem Modelling and Optimization, P. Kall, ed., Springer, 1992, pp. 580–587.

  29. P. Kall and J. Mayer, Model management for stochastic linear programming, Working Paper, University of Zürich, Zürich, Switzerland, 1993.

    Google Scholar 

  30. P. Kall, A. Ruszczyński and K. Frauendorfer, Approximation techniques in stochastic programming, inNumerical Techniques for Stochastic Optimization, Yu. Ermoliev and R.J-B Wets, eds., Springer Series in Computational Mathematics, Vol. 10, Springer, Berlin, 1988, pp. 33–64.

    Google Scholar 

  31. R. Krishnan, Model management: Survey, future research directions and a bibliography, ORSA Computer Science Technical Section Newsletter 14, Spring 1993, 1–16.

    Google Scholar 

  32. C.A.C. Kuip, Algebraic languages for mathematical programming, European Journal of Operational Research 67, 1993, 25–51.

    Article  Google Scholar 

  33. M. Lane and P. Hutchinson, A model for managing a certificate of deposit portfolio under uncertainty, inStochastic Programming, M.A.H. Dempster, ed., Academic Press, London, 1980.

    Google Scholar 

  34. I.J. Lustig, J.M. Mulvey and T.J. Carpenter, The formulation of stochastic programs for interior methods, Technical Report SOR 89-16, Department of Civil Engineering and Operations Research, Princeton University, Princeton, NJ, 1989.

    Google Scholar 

  35. P. Ma, F.H. Murphy and E.A. Stohr, An implementation of LPFORM, Working Paper, University of Delaware, Newark, DE, 1994.

    Google Scholar 

  36. J.M. Mulvey and H. Vladimirou, Stochastic network optimization models for investment planning, Annals of Operations Research 20, 1989, 187–217.

    MathSciNet  Google Scholar 

  37. A. Prékopa, Numerical solutions of probabilistic constrained programming problems, inNumerical Techniques for Stochastic Optimization, Yu. Ermoliev and R.J-B Wets, eds., Springer Series in Computational Mathematics, Vol. 10, Springer, Berlin, 1988, pp. 123–139.

    Google Scholar 

  38. R.T. Rockafellar and R.J-B Wets, Scenarios and policy aggregation in optimization under uncertainty, Mathematics of Operations Research 16, 1991, 119–148.

    Google Scholar 

  39. A. Ruszczyński, A regularized decomposition method for minimizing a sum of polyhedral functions, Mathematical Programming 35, 1986, 309–333.

    Article  Google Scholar 

  40. A. Ruszczyński, Parallel decomposition of multistage stochastic programs, Mathematical Programming 58, 1992, 201–228.

    Article  Google Scholar 

  41. K. Schittkowski, EMP: An expert system for mathematical programming, Technical Report, Mathematisches Institut, Universität Bayreuth, 1987.

  42. K. Schittkowski, Some experiments on heuristic code selection numerical performance in nonlinear programming, European Journal of Operational Research 65, 1993, 292–304.

    Article  Google Scholar 

  43. L. Schrage,Linear, Integer and Quadratic Programming with LINDO, 3rd ed., The Scientific Press, Palo Alto, CA, 1986.

    Google Scholar 

  44. S. Sen, R.D. Doverspike and S. Cosares, Network planning with random demand, Working paper, Department of Systems and Industrial Engineering, University of Arizona, Tucson, AZ, 1992.

    Google Scholar 

  45. B. Shetty, H.K. Bhargava and R. Krishnan (eds.),Model Management in Operations Research, Annals of Operations Research 38, 1992.

  46. T. Szántai, A computer code for solution of probabilistic-constrained stochastic programming problems, inNumerical Techniques for Stochastic Optimization, Yu. Ermoliev and R.J-B Wets, eds., Springer Series in Computational Mathematics, Vol. 10, Springer, Berlin, 1988, pp. 229–235.

    Google Scholar 

  47. R. Van Slyke and R.J-B Wets, L-shaped linear programs with applications to optimal control theory and stochastic programming, SIAM Journal of Applied Mathematics 17, 1969, 638–663.

    Article  Google Scholar 

  48. S.W. Wallace and R.J-B Wets, Preprocessing in stochastic programming: the case of uncapacitated networks, ORSA Journal on Computing 1, 1989, 252–270.

    Google Scholar 

  49. S.W. Wallace and R.J-B Wets, Preprocessing in stochastic programming: the case of linear programs, ORSA Journal on Computing 4, 1992, 45–59.

    MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Business Administration, Dalhousie University, B3H 1Z5, Halifax, Nova Scotia, Canada

    H. I. Gassmann & A. M. Ireland

Authors
  1. H. I. Gassmann
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A. M. Ireland
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gassmann, H.I., Ireland, A.M. On the formulation of stochastic linear programs using algebraic modelling languages. Ann Oper Res 64, 83–112 (1996). https://doi.org/10.1007/BF02187642

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02187642

Keywords

Search

Navigation