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.
Similar content being viewed by others
References
J.F. Benders, Partitioning procedures for solving mixed-variables programming problems, Numerische Mathematik 4(1962)238–252.
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.
J.R. Birge, Decomposition and partitioning methods for multistage stochastic linear programs, Operations Research 33(1985)989–1007.
J.R. Birge and L.Q. Qi, Computing block-angular Karmarkar projections with applications to stochastic programming, Management Sci. 34(1988)1472–1479.
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.
J.R. Birge, Stochastic programming computation and applications, INFORMS J. Comput. 9(1997) 111–133.
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.
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.
B.J. Chun and S.M. Robinson, Scenario analysis via bundle decomposition, Annals of Operations Research 56(1995)39–63.
G.B. Dantzig, Linear programming under uncertainty, Management Sci. 1(1955)197–206.
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.
G. Dantzig and P. Wolfe, Decomposition principle for linear programs, Operations Research 8 (1960)101–111.
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.
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.
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.
P.W. Glynn and D.L. Iglehart, Importance sampling for stochastic simulation, Management Science 35(1989)1367–1392.
J.L. Higle and S. Sen, Stochastic Decomposition: A Statistical Method for Large Scale Stochastic Linear Programming, Kluwer, Dordrecht, 1996.
J.-B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithm, Springer, Berlin, 1993.
G. Infanger, Planning under Uncertainty: Solving Large-Scale Stochastic Linear Programs, Boyd and Fraser, Danvers, 1994.
P. Kall and S.W. Wallace, Stochastic Programming, Wiley, Chichester, 1994.
K.C. Kiwiel, Methods of Descent for Nondifferentiable Optimization, Lecture Notes in Mathematics 1133, Springer, Berlin, 1985.
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.
W.K. Klein Haneveld and M.H. van der Vlerk, Stochastic integer programming: General models and algorithms, Annals of Operations Research, this volume.
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.
P.L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM Journal on Numerical Analysis 16(1979)964–979.
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.
K. Marti, Differentiation formulas for probability functions: The transformation method, Mathematical Programming, Series B 75(1996)201–220.
J.M. Mulvey and A. Ruszczyński, A new scenario decomposition method for large-scale stochastic optimization, Operations Research 43(1995)477–490.
V.I. Norkin, Yu.M. Ermoliev and A. Ruszczyński, On optimal allocation of indivisibles under uncertainty, Operations Research, to appear.
G.Ch. Pflug, Optimization of Stochastic Models: The Interface Between Simulation and Optimization, Kluwer, Dordrecht, 1996.
A. Prékopa, Stochastic Programming, Kluwer, Dordrecht, 1995.
S.M. Robinson, Analysis of sample path optimization, Mathematics of Operations Research 21 (1996)513–528.
R.T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, 1973.
R.T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM Journal on Control and Optimization 14(1976)877–898.
R.T. Rockafellar, Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Mathematics of Operations Research 1(1976)97–116.
R.T. Rockafellar and R.J-B Wets, Scenarios and policy aggregation in optimization under uncertainty, Mathematics of Operations Research 16(1991)1–23.
W. Römisch and R. Schultz, Lipschitz stability for stochastic programs with complete recourse, SIAM Journal on Optimization 6(1966)531–547.
C.H. Rosa and A. Ruszczyński, On augmented Lagrangian decomposition methods for multistage stochastic programs, Annals of Operations Research 64(1996)289–309.
A. Ruszczyński, A regularized decomposition method for minimizing a sum of polyhedral functions, Mathematical Programming 35(1986)309–333.
A. Ruszczyński, A linearization method for nonsmooth stochastic optimization problems, Mathematics of Operations Research 12(1987)32–49.
A. Ruszczyński, On convergence of an augmented Lagrangian decomposition method for sparse convex optimization, Mathematics of Operations Research 20(1995)634–656.
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.
J.E. Spingarn, Application of the method of partial inverses to convex programming: Decomposition, Mathematical Programming 32(1985)199–233.
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.
A. Świetanowski, A penalty based simplex method for linear programming, Working Paper WP–95–005, International Institute for Applied Systems Analysis, Laxenburg, Austria, 1995.
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.
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.
R.J-B Wets, Challenges in stochastic programming, Mathematical Programming, Series B 75 (1996) 115–135.
Rights 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
Issue Date:
DOI: https://doi.org/10.1023/A:1018965626303