Abstract
A new decomposition method for multistage stochastic linear programming problems is proposed. A multistage stochastic problem is represented in a tree-like form and with each node of the decision tree a certain linear or quadratic subproblem is associated. The subproblems generate proposals for their successors and some backward information for their predecessors. The subproblems can be solved in parallel and exchange information in an asynchronous way through special buffers. After a finite time the method either finds an optimal solution to the problem or discovers its inconsistency. An analytical illustrative example shows that parallelization can speed up computation over every sequential method. Computational experiments indicate that for large problems we can obtain substantial gains in efficiency with moderate numbers of processors.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
D.P. Bertsekas, “Distributed dynamic programming,”IEEE Transactions on Automatic Control AC-27 (1982) 610–616.
D.P. Bertsekas and J.N. Tsitsiklis,Parallel and Distributed Computation (Prentice-Hall, Englewood Cliffs, NJ, 1989).
J.R. Birge, “Decomposition and partitioning methods for multistage stochastic linear programs,”Operations Research 33 (1985) 989–1007.
J.R. Birge and F.V. Louveaux, “A multicut algorithm for two-stage stochastic linear programs,”European Journal of Operations Research 34 (1988) 384–392.
J. Bisschop and A. Meeraus, “Matrix augmentation and partitioning in the updating of the basis inverse,”Mathematical Programming 30 (1984) 71–87.
G.B. 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, Vol. I (University of California Press, Berkeley, CA, 1961) pp. 165–176.
G.B. Dantzig and P. Wolfe, “Decomposition principle for linear programs,”Operations Research 8 (1960) 101–111.
R. Entriken, “The parallel decomposition of linear programs,” Technical Report SOL 89-17, Department of Operations Research, Stanford University (Stanford, CA, 1989).
F. Fourer, “Solving staircase linear programs by the simplex method, 1: Inversion,”Mathematical Programming 23 (1982) 274–313.
F. Fourer, “Solving staircase linear programs by the simplex method, 2: Pricing,”Mathematical Programming 25 (1983) 251–292.
H.I. Gassmann, “MSLiP: A computer code for the multistage stochastic linear programming problem,”Mathematical Programming 47 (1990) 407–423.
J. Gondzio and A. Ruszczyński, “A sensitivity method for solving multistage stochastic linear programming problems,” in: A. Lewandowski and A. Wierzbicki, eds.,Aspiration Based Decision Support Systems, Lecture Notes in Economics and Mathematical Systems No. 331 (Springer, Berlin, 1989) pp. 68–79.
J.K. Ho, T.C. Lee and R.P. Sundarraj, “Decomposition of linear programs using parallel computation,” Technical Report, College of Business Administration, University of Tennessee (Knoxville, TN, 1987).
J.K. Ho and A.S. Manne, “Nested decomposition for dynamic models,”Mathematical Programming 6 (1974) 121–140.
P. Kall, “Computational methods for solving two-stage stochastic linear programming problems,”ZAMT 30 (1979) 261–271.
K.C. Kiwiel, “A dual method for solving certain positive semidefinite quadratic programming problems,”SIAM Journal on Scientific and Statistical Computing 10 (1989) 175–186.
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.
J.M. Mulvey and H. Vladimirou, “Evaluation of a parallel hedging algorithm for stochastic network programming,” in: R. Sharda, B.L. Golden, E. Wasil, O. Balci and W. Stewart, eds.,Impact of Recent Computer Advances on Operations Research (North-Holland, Amsterdam, 1989) pp. 106–119.
B. Murtaugh,Advanced Linear Programming (McGraw-Hill, New York, 1981).
A. Propoi and V. Krivonozhko, “The simplex method for dynamic linear programs,” Research Report RR-78-14, International Institute for Applied Systems Analysis (Laxenburg, 1978).
R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, NJ, 1970).
R.T. Rockafellar and R.J.-B. Wets, “A Lagrangian finite generation technique for solving linear quadratic problems in stochastic programming,”Mathematical Programming Study 28 (1986) 63–93.
R.T. Rockafellar and R.J.-B. Wets, “Scenarios and policy aggregation in optimization under uncertainty,”Mathematics of Operations Research 16 (1991) 119–147.
A. Ruszczyński, “A regularized decomposition method for minimizing a sum of polyhedral functions,”Mathematical Programming 35 (1986) 309–333.
A. Ruszczyński, “Parallel decomposition of multistage stochastic programming problems,” Working Paper WP-88-094, International Institute for Applied Systems Analysis (Laxenburg, 1988).
A. Ruszczyński, “Modern techniques for linear dynamic and stochastic programs,” in: A. Lewandowski and A. Wierzbicki, eds.,Aspiration Based Decision Support Systems, Lecture Notes in Economics and Mathematical Systems No. 331 (Springer, Berlin, 1989) pp. 48–67.
A. Ruszczyński, “Regularized decomposition and augmented Lagrangian decomposition for angular linear programming problems,” in: A. Lewandowski and A. Wierzbicki, eds.,Aspiration Based Decision Support Systems, Lecture Notes in Economics and Mathematical Systems No. 331 (Springer, Berlin, 1989) pp. 80–91.
A. Ruszczyński, “An augmented Lagrangian decomposition method for block diagonal linear programming problems,”Operations Research Letters 8 (1989) 287–294.
J. Sobczyk, “Multitasking in TURBO PASCAL,” Technical Report, Institute of Automatic Control, Warsaw University of Technology (Warsaw, 1989).
B. Strazicky, “Some results concerning an algorithm for the discrete recourse problem,” in: M. Dempster, ed.,Stochastic Programming (Academic Press, London, 1980) pp. 263–274.
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: Yu. Ermoliev and R.J.-B. Wets, eds.,Numerical Techniques for Stochastic Optimization (Springer, Berlin, 1988) pp. 65–94.
R. Wittrock, “Dual nested decomposition of staircase linear programs,”Mathematical Programming Study 24 (1985) 65–86.
Author information
Authors and Affiliations
Additional information
This work was partly supported by the International Institute for Applied Systems Analysis, Laxenburg, Austria.
Rights and permissions
About this article
Cite this article
Ruszczyński, A. Parallel decomposition of multistage stochastic programming problems. Mathematical Programming 58, 201–228 (1993). https://doi.org/10.1007/BF01581267
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01581267