Skip to main content
SpringerLink
Log in

Some advances in decomposition methodsfor stochastic linear programming

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

Abstract

Stochastic programming problems have very large dimension and characteristic structureswhich are tractable by decomposition. We review some new developments in cutting planemethods, augmented Lagrangian and splitting methods for linear multi‐stage stochasticprogramming problems.

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. J.F. Benders, Partitioning procedures for solving mixed-variables programming problems, Numerische Mathematik 4(1962)238–252.

    Google Scholar 

  2. A.J. Berger, J.M. Mulvey and A. Ruszczyński, An extension of the DQA algorithm to convex stochastic programs, SIAM Journal on Optimization 4(1994)735–753.

    Google Scholar 

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

    Google Scholar 

  4. J.R. Birge and L.Q. Qi, Computing block-angular Karmarkar projections with applications to stochastic programming, Management Sci. 34(1988)1472–1479.

    Google Scholar 

  5. J.R. Birge, C.J. Donohue, D.F. Holmes and O.G. Svintsitski, A parallel implementation of the nested decomposition method for multistage stochastic linear programs, Mathematical Programming, Series B 75(1996)327–352.

    Google Scholar 

  6. J.R. Birge, Stochastic programming computation and applications, INFORMS J. Comput. 9(1997) 111–133.

    Google Scholar 

  7. J.R. Birge and F.V. Louveaux, A multicut algorithm for two-stage stochastic linear programs, European Journal of Operational Research 34(1988)384–392.

    Google Scholar 

  8. 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)284–298.

    Google Scholar 

  9. B.J. Chun and S.M. Robinson, Scenario analysis via bundle decomposition, Annals of Operations Research 56(1995)39–63.

    Google Scholar 

  10. G.B. Dantzig, Linear programming under uncertainty, Management Sci. 1(1955)197–206.

    Google Scholar 

  11. G. Dantzig and A. Madansky, On the solution of two-stage linear programs under uncertainty, in: Proceedings of the 4th Berkeley Symposium on Mathematical Statistics and Probability, University of California Press, Berkeley, 1961, pp. 165–176.

    Google Scholar 

  12. G. Dantzig and P. Wolfe, Decomposition principle for linear programs, Operations Research 8 (1960)101–111.

    Google Scholar 

  13. J. Eckstein and D.P. Bertsekas, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Mathematical Programming 55(1992)293–318.

    Google Scholar 

  14. Yu.M. Ermoliev, Stochastic quasigradient methods, in: Numerical Techniques for Stochastic Optimization, eds. Yu.M. Ermoliev and R.J-B Wets, Springer, Berlin, 1988, pp. 141–185.

    Google Scholar 

  15. D. Gabay, Applications of the method of multipliers to variational inequalities, in: Augmented Lagrangian Methods: Applications to the Solution of Boundary-Value Problems, eds. M. Fortin and R. Glowinski, North-Holland, Amsterdam, 1983.

    Google Scholar 

  16. P.W. Glynn and D.L. Iglehart, Importance sampling for stochastic simulation, Management Science 35(1989)1367–1392.

    Google Scholar 

  17. J.L. Higle and S. Sen, Stochastic Decomposition: A Statistical Method for Large Scale Stochastic Linear Programming, Kluwer, Dordrecht, 1996.

    Google Scholar 

  18. J.-B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithm, Springer, Berlin, 1993.

    Google Scholar 

  19. G. Infanger, Planning under Uncertainty: Solving Large-Scale Stochastic Linear Programs, Boyd and Fraser, Danvers, 1994.

    Google Scholar 

  20. P. Kall and S.W. Wallace, Stochastic Programming, Wiley, Chichester, 1994.

    Google Scholar 

  21. K.C. Kiwiel, Methods of Descent for Nondifferentiable Optimization, Lecture Notes in Mathematics 1133, Springer, Berlin, 1985.

    Google Scholar 

  22. K.C. Kiwiel, C.H. Rosa and A. Ruszczyński, Decomposition via alternating linearization, Working Paper WP–95–051, International Institute for Applied Systems Analysis, Laxenburg, 1995.

    Google Scholar 

  23. W.K. Klein Haneveld and M.H. van der Vlerk, Stochastic integer programming: General models and algorithms, Annals of Operations Research, this volume.

  24. 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 

  25. P.L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM Journal on Numerical Analysis 16(1979)964–979.

    Google Scholar 

  26. I.J. Lustig, J.M. Mulvey and T.J. Carpenter, Formulating two-stage stochastic programs for interior point methods, Operations Research 39(1991)757–770.

    Google Scholar 

  27. K. Marti, Differentiation formulas for probability functions: The transformation method, Mathematical Programming, Series B 75(1996)201–220.

    Google Scholar 

  28. J.M. Mulvey and A. Ruszczyński, A new scenario decomposition method for large-scale stochastic optimization, Operations Research 43(1995)477–490.

    Google Scholar 

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

  30. G.Ch. Pflug, Optimization of Stochastic Models: The Interface Between Simulation and Optimization, Kluwer, Dordrecht, 1996.

    Google Scholar 

  31. A. Prékopa, Stochastic Programming, Kluwer, Dordrecht, 1995.

    Google Scholar 

  32. S.M. Robinson, Analysis of sample path optimization, Mathematics of Operations Research 21 (1996)513–528.

    Google Scholar 

  33. R.T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, 1973.

    Google Scholar 

  34. R.T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM Journal on Control and Optimization 14(1976)877–898.

    Google Scholar 

  35. R.T. Rockafellar, Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Mathematics of Operations Research 1(1976)97–116.

    Google Scholar 

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

    Google Scholar 

  37. W. Römisch and R. Schultz, Lipschitz stability for stochastic programs with complete recourse, SIAM Journal on Optimization 6(1966)531–547.

    Google Scholar 

  38. C.H. Rosa and A. Ruszczyński, On augmented Lagrangian decomposition methods for multistage stochastic programs, Annals of Operations Research 64(1996)289–309.

    Google Scholar 

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

    Google Scholar 

  40. A. Ruszczyński, A linearization method for nonsmooth stochastic optimization problems, Mathematics of Operations Research 12(1987)32–49.

    Google Scholar 

  41. A. Ruszczyński, On convergence of an augmented Lagrangian decomposition method for sparse convex optimization, Mathematics of Operations Research 20(1995)634–656.

    Google Scholar 

  42. A. Ruszczyński and A. Swietanowski, Accelerating the regularized decomposition method for two stage stochastic linear problems, European Journal of Operational Research 101(1997)328–342.

    Google Scholar 

  43. J.E. Spingarn, Application of the method of partial inverses to convex programming: Decomposition, Mathematical Programming 32(1985)199–233.

    Google Scholar 

  44. G. Stephanopoulos and W. Westerberg, The use of Hestenes' method of multipliers to resolve dual gaps in engineering system optimization, Journal of Optimization Theory and Applications 15 (1975)285–309.

    Google Scholar 

  45. A. Świetanowski, A penalty based simplex method for linear programming, Working Paper WP–95–005, International Institute for Applied Systems Analysis, Laxenburg, Austria, 1995.

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

    Google Scholar 

  47. R.J-B Wets, Large scale linear programming techniques in stochastic programming, in: Numerical Techniques for Stochastic Optimization, eds. Yu.M. Ermoliev and R.J-B Wets, Springer, Berlin, 1988, pp. 65–93.

    Google Scholar 

  48. R.J-B Wets, Challenges in stochastic programming, Mathematical Programming, Series B 75 (1996) 115–135.

    Google Scholar 

Download references

Authors
  1. Andrzej Ruszczynski
    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

Ruszczynski, A. Some advances in decomposition methodsfor stochastic linear programming. Annals of Operations Research 85, 153–172 (1999). https://doi.org/10.1023/A:1018965626303

Download citation

  • Issue Date:

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

Keywords

Search

Navigation