Skip to main content
SpringerLink
Log in

Stochastic integer programming:General models and algorithms

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

Abstract

We survey structural properties of and algorithms for stochastic integer programmingmodels, mainly considering linear two‐stage models with mixed‐integer recourse (and theirmulti‐stage extensions).

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. Z. Artstein and R.J-B. Wets, Stability results for stochastic programs and sensors, allowing for discontinuous objective functions, SIAM Journal on Optimization 4(1994)537–550.

    Google Scholar 

  2. I.L. Averbakh, An iterative method of solving two-stage discrete stochastic programming problems with additively separable variables, USSR Computational Mathematics and Mathematical Physics 31(1991)21–27.

    Google Scholar 

  3. J.R. Birge and M.A.H. Dempster, Stochastic programming approaches to stochastic scheduling, Journal of Global Optimization 9(1996)417–451.

    Google Scholar 

  4. C.C. Carøe, A. Ruszczyński and R. Schultz, Unit commitment under uncertainty via two-stage stochastic programming, in: Proceedings of NOAS 97, eds. C.C. Carøe and D. Pisinger, Technical Report DIKU-TR-97/23, Department of Computer Science, University of Copenhagen, 1997, pp. 21–30. Paper with improved computational results available as SC 98–11 via http://www.zib.de/bib/pub/pw/index.en.html.

  5. C.C. Carøe and R. Schultz, Dual decomposition in stochastic integer programming, Preprint SC 96–46, Konrad-Zuse-Zentrum für Informationstechnik Berlin, 1996.

  6. C.C. Carøe and J. Tind, L-shaped decomposition of two-stage stochastic programs with integer recourse, Technical Report, Institute of Mathematics, University of Copenhagen, 1995, to appear in Mathematical Programming.

  7. C.C. Carøe and J. Tind, A cutting-plane approach to mixed 0–1 stochastic integer programs, European Journal of Operational Research 101(1997)306–316.

    Google Scholar 

  8. D. Dentcheva and W. Römisch, Optimal power generation under uncertainty via stochastic programming, Preprint 96–35, Humboldt-Universität Berlin, Institut für Mathematik, 1996, to appear in K. Marti and P. Kall (eds.), Stochastic Programming Methods and Technical Applications, Lecture Notes in Economics and Mathematical Systems 458, Springer, Berlin, 1998. Revised version available at http://elib.zib.de/echtzeit/abstracts/Preprint–97–6.

  9. C.L. Dert, Asset liability management for pension funds, a multistage chance constrained programming approach, Ph.D. Thesis, Erasmus University, Rotterdam, The Netherlands, 1995.

    Google Scholar 

  10. M. Dyer and L. Stougie, Stochastic programming problems: Complexity and approximability, in preparation.

  11. M.R. Garey and D.S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, Freeman, New York, 1979.

    Google Scholar 

  12. T.W. Jonsbräten, R.J-B. Wets and D.L. Woodruff, A class of stochastic programs with decision dependent random elelements, Annals of Operations Research, to appear.

  13. P. Kall and J. Mayer, SLP-IOR: An interactive model management system for stochastic linear programs, Mathematical Programming 75(1996)221–240.

    Google Scholar 

  14. W.K. Klein Haneveld, L. Stougie and M.H. van der Vlerk, Some theorems on the convex hull of a function with an application to stochastic integer programming, Discussion Paper TI 94–81, Tinbergen Institute, Amsterdam/Rotterdam, 1994.

    Google Scholar 

  15. W.K. Klein Haneveld, L. Stougie and M.H. van der Vlerk, On the convex hull of the simple integer recourse objective function, Annals of Operations Research 56(1995)209–224.

    Google Scholar 

  16. W.K. Klein Haneveld, L. Stougie and M.H. van der Vlerk, An algorithm for the construction of convex hulls in simple integer recourse programming, Annals of Operations Research 64(1996) 67–81.

    Google Scholar 

  17. W.K. Klein Haneveld, L. Stougie and M.H. van der Vlerk, Convex approximations for simple integer recourse models by perturbing the underlying distribution, Research Report 97A19, SOM, University of Groningen, 1997.

  18. W.K. Klein Haneveld, L. Stougie and M.H. van der Vlerk, Convex simple integer recourse problems, Research Report 97A10, SOM, University of Groningen, 1997.

  19. W.K. Klein Haneveld and M.H. van der Vlerk, On the expected value function of a simple integer recourse problem with random technology matrix, Journal of Computational and Applied Mathematics 56(1994)45–53.

    Google Scholar 

  20. B.J. Lageweg, J.K. Lenstra, A.H.G. Rinnooy Kan and L. Stougie, Stochastic integer programming by dynamic programming, Statistica Neerlandica 39(1985)97–113.

    Google Scholar 

  21. G. Laporte and F.V. Louveaux, The integer L-shaped method for stochastic integer programs with complete recourse, Operations Research Letters 13(1993)133–142.

    Google Scholar 

  22. G. Laporte, F.V. Louveaux, and H. Mercure, The vehicle routing problem with stochastic travel times, Transportation Science 26(1992)161–170.

    Google Scholar 

  23. G. Laporte, F.V. Louveaux and L. van Hamme, Exact solution of a stochastic location problem by an integer L-shaped algorithm, Transportation Science 28(1994)95–103.

    Google Scholar 

  24. A. Løkketangen and D.L. Woodruff, Progressive hedging and tabu search applied to mixed integer (0, 1) multistage stochastic programming, Journal of Heuristics 2(1996)111–128.

    Google Scholar 

  25. F.V. Louveaux and M.H. van der Vlerk, Stochastic programming with simple integer recourse, Mathematical Programming 61(1993)301–325.

    Google Scholar 

  26. G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization, Wiley, New York, 1988.

    Google Scholar 

  27. A. Prékopa, Stochastic Programming, Kluwer Academic, Dordrecht, 1995.

    Google Scholar 

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

    Google Scholar 

  29. A. Ruszczyński, Y. Ermoliev and V. Norkin, On optimal allocation of indivisibles under uncertainty, Operations Research, to appear.

  30. R. Schultz, Continuity and stability in two-stage stochastic integer programming, in: Lecture Notes in Economics and Mathematical Systems, Vol. 379, ed. K. Marti, Springer, Berlin, 1992, pp. 81–92.

    Google Scholar 

  31. R. Schultz, Continuity properties of expectation functions in stochastic integer programming, Mathematics of Operations Research 18(1993)578–589.

    Google Scholar 

  32. R. Schultz, On structure and stability in stochastic programs with random technology matrix and complete integer recourse, Mathematical Programming 70(1995)73–89.

    Google Scholar 

  33. R. Schultz, Rates of convergence in stochastic programs with complete integer recourse, SIAM Journal on Optimization 6(4)(1996)1138–1152.

    Google Scholar 

  34. R. Schultz, L. Stougie and M.H. van der Vlerk, Solving stochastic programs with complete integer recourse: A framework using Gröbner bases, Discussion Paper 9562, CORE, Louvain-la-Neuve, Belgium, 1995; revision to appear in Mathematical Programming.

    Google Scholar 

  35. L. Stougie, Design and Analysis of Algorithms for Stochastic Integer Programming, Vol. 37 of CWI Tracts, Centrum voor Wiskunde en Informatica, Amsterdam, 1987.

    Google Scholar 

  36. L. Stougie and M.H. van der Vlerk, Stochastic integer programming, in: Annotated Bibliographies in Combinatorial Optimization, eds. M. Dell'Amico, F. Maffioli and S. Martello, Wiley, 1997, chap. 9, pp. 127–141.

  37. S. Takriti, J.R. Birge and E. Long, A stochastic model for the unit commitment problem, IEEE Transactions on Power Systems 11(1996)1497–1508.

    Google Scholar 

  38. S. Takriti, B. Krasenbrink and L.S.-Y. Wu, Incorporating fuel constraints and electricity spot prices into the stochastic unit commitment problem, IBM Research Report RC 21066, Mathematical Sciences Department, IBM Research Division, T.J. Watson Research Center, Yorktown Heights, New York, 1997.

    Google Scholar 

  39. S.R. Tayur, R.R. Thomas and N.R. Natraj, An algebraic geometry algorithm for scheduling in the presence of setups and correlated demands, Mathematical Programming 69(1995)369–401.

    Google Scholar 

  40. A. Tomasgard, S. Dye, S.W. Wallace, J.A. Audestad, L. Stougie and M.H. van der Vlerk, Modelling in distributed telecommunications networks, Discussion Paper TI 97–030/4, Tinbergen Institute, Amsterdam/Rotterdam, 1997, to appear in Annals of Operations Research.

    Google Scholar 

  41. M.H. van der Vlerk, Stochastic programming with integer recourse, Ph.D. Thesis, University of Groningen, The Netherlands, 1995.

    Google Scholar 

  42. M.H. van der Vlerk, Stochastic programming bibliography, available via http://mally.eco.rug.nl, 1996–1998.

  43. R. Van Slyke and R.J-B. Wets, L-shaped linear programs with applications to control and stochastic programming, SIAM Journal on Applied Mathematics 17(1969)638–663.

    Google Scholar 

  44. R.M. Wollmer, Two-stage linear programming under uncertainty with 0–1 first-stage variables, Mathematical Programming 19(1980)279–288.

    Google Scholar 

  45. W. Ziemba and J. Mulvey (eds.), World Wide Asset and Liability Management, Cambridge University Press, to appear.

Download references

Authors
  1. Willem K. Klein Haneveld
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Maarten H. van der Vlerk
    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

Klein Haneveld, W.K., van der Vlerk, M.H. Stochastic integer programming:General models and algorithms. Annals of Operations Research 85, 39–57 (1999). https://doi.org/10.1023/A:1018930113099

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1018930113099

Keywords

Search

Navigation