摘要: A new decomposition method for multistage stochastic linear programming problems is proposed. problem represented in a tree-like form and with each node of the decision tree certain or quadratic subproblem associated. The subproblems generate proposals their successors some backward information predecessors. can be solved parallel exchange an asynchronous way through special buffers. After finite time either finds optimal solution to discovers its inconsistency. An analytical illustrative example shows that parallelization speed up computation over every sequential method. Computational experiments indicate large we obtain substantial gains efficiency moderate numbers processors.
springer.com
iiasa.ac.at参考文章(31)
Jacek Gondzio, Andrzej Ruszczynski, A Sensitivity Method for Solving Multistage Stochastic Linear Programming Problems Springer, Berlin, Heidelberg. pp. 68- 79 ,(1989) , 10.1007/978-3-662-21637-8_4
Robert J. Wittrock, Dual nested decomposition of staircase linear programs Mathematical Programming Essays in Honor of George B. Dantzig Part I. pp. 65- 86 ,(1985) , 10.1007/BFB0121043
Andrzej Ruszczynski, Modern Techniques for Linear Dynamic and Stochastic Programs Springer, Berlin, Heidelberg. pp. 48- 67 ,(1989) , 10.1007/978-3-662-21637-8_3
R. T. Rockafellar, R. J.-B. Wets, A Lagrangian finite generation technique for solving linear-quadratic problems in stochastic programming Mathematical Programming Studies. pp. 63- 93 ,(1986) , 10.1007/BFB0121126
George B. Dantzig, Albert Medansky, On the Solution of Two-stage Linear Programs under Uncertainty Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics. pp. 165- 176 ,(1961)
R.P. Sundarraj, T.C. Lee, J.K. Ho, Decomposition of linear programs using parallel computation. Technical report ,(1988)
J.N. Tsitsiklis, D.P. Bertsekas, Parallel and distributed computation Old Tappan, NJ (USA); Prentice Hall Inc.. ,(1989)
Michael J. Best, Equivalence of some quadratic programming algorithms Mathematical Programming. ,vol. 30, pp. 71- 87 ,(1984) , 10.1007/BF02591799
R. T. Rockafellar, Roger J.-B. Wets, Scenarios and policy aggregation in optimization under uncertainty Mathematics of Operations Research. ,vol. 16, pp. 119- 147 ,(1991) , 10.1287/MOOR.16.1.119
John R. Birge, François V. Louveaux, A multicut algorithm for two-stage stochastic linear programs European Journal of Operational Research. ,vol. 34, pp. 384- 392 ,(1988) , 10.1016/0377-2217(88)90159-2