We develop an algorithm for solving two-stage sto chastic linear programs with network recourse. The algorithm is based on the proximal minimization algo rithm with D-functions and uses a primal-dual row- action algorithm to solve the resulting, strictly convex subproblems. The stochastic program is reformulated into a form that decomposes by scenario, thus making the algorithm suitable for parallel implementation. In addition, the constraints of each scenario subproblem (which are network problems) can be iterated upon concurrently, allowing for a massively parallel imple mentation. The algorithm is implemented on a Con nection Machine 2 with up to 32k processors. It is shown to be very effective in solving problems with up to 2,048 scenarios, where the deterministic equivalent program has 217,103 constraints and 618,529 variables.
Get full access to this article
View all access options for this article.
References
1.
Ariyawansa, K.A., and Hudson, D.D.1989. Performance of a benchmark parallel implementation of the Van Slyke and Wets algorithm for two-stage stochastic programs on the Sequent/Balance. Technical Report. Pullman: Department of Pure and Applied Mathematics, Washington State University .
2.
Ariyawansa, K.A., Sorensen, D.C., and Wets, R. J-B .1990. Parallel schemes to approximate values and subgradients of the recourse function in certain stochastic programs. Technical Report. Pullman: Department of Pure and Applied Mathematics, Washington State University.
3.
Beale, E.M.L.1955. On minimizing a convex function subject to linear inequalities . J. Roy. Statist. Soc.17B:173-184.
4.
Birge, J.R.1982. The value of the stochastic solution in stochastic linear programs with fixed recourse. Math. Programming24:314-325.
5.
Birge, J.R.1985. Decomposition and partitioning methods for multistage stochastic linear programs. Oper. Res. 33(5):989-1007.
6.
Brooke, A., Kendrick, D., and Meeraus, A.1988. GAMS: a user's guide. Scientific Press .
7.
Censor, Y.1981. Row-action methods for huge and sparse systems and their applications. SIAM Rev.23:444-464.
8.
Censor, Y., and Lent, A.1981. An iterative row-action method for interval convex programming . J. Optim. Theory Appl.34:321-353.
9.
Censor, Y., De Pierro, A.R., Elfving, T., Herman, G.T., and Iusem, A.N.1990. On iterative methods for linearly constrained entropy maximization. In Numerical analysis and mathematical modelling, vol. 24, edited by A. Wakulicz.Warsaw, Poland: Banach Center Publications, PWN-Polish Scientific Publisher, pp. 145-163.
10.
Censor, Y., and Zenios, S.A.1992. The proximal minimization algorithm with D-functions . J. Optim. Theory Appl.73(3):455-468.
11.
Dantzig, G.B.1955. Linear programming under uncertainty. Management Sci.1:197-206.
12.
Dantzig, G.B.1985. Planning under uncertainty using parallel computing. Ann . Oper. Res.14:1-17.
13.
Dantzig, G. B., Dempster, M. A. H., and Kallio, M. J., eds. 1981. Large-scale linear programming, vol. 1. IIASA collaborative proceedings series. CP-81-51. Laxenburg, Austria: International Institute for Applied Systems Analysis.
14.
Dantzig, G.B., and Glynn, P.W.1990. Parallel processors for planning under uncertainty. Ann . Oper. Res.22:1-21.
15.
Dantzig, G.B., and Madansky, A.1961. On the solution of two-stage linear programs under uncertainty . In Proceedings of the fourth Berkeley symposium on mathematical statistics and probability, edited by J. Neyman. Berkeley: University of California Press, pp. 165-176.
16.
Eriksson, J.R.1985. An iterative primal-dual algorithm for linear programming. Technical Report LiTH-MAT-R-1985-10. Linkøping, Sweden: Department of Mathematics, Linkøping University.
17.
Gassmann, H.I.1990. MSLiP: a computer code for the multistage stochastic linear programming problem. Math. Programming47:407-423.
18.
Lustig, I.J., Mulvey, J.M., and Carpenter, T.J.1991. Formulating stochastic programs for interior point methods . Oper. Res.39(5):757-770.
19.
Madansky, A.1960. Inequalities for stochastic linear programming problems . Management Sci.6:197-204.
20.
Mulvey, J.M., and Ruszczynski, A.1993. A diagonal quadratic approximation method for large scale linear programs. Oper. Res. Lett., in press.
21.
Mulvey, J.M., and Vladimirou, H.1991a. Applying the progressive hedging algorithm to stochastic generalized networks. Ann. Oper. Res.31:399-424.
22.
Mulvey, J.M., and Vladimirou, H.1991b. Solving multistage stochastic networks: an application of scenario aggregation. Networks21:619-643.
23.
Nielsen, S.S., and Zenios, S.A.1992a. Massively parallel algorithms for singly constrained nonlinear programs. ORSA J. Computing4(2):166-181.
24.
Nielsen, S.S., and Zenios, S.A.1992b. Solving multistage stochastic network programs. Technical Report 92-08-04. Philadelphia: Decision Sciences Department, The Wharton School, University of Pennsylvania .
25.
Nielsen, S.S., and Zenios, S.A.1992c. A stochastic programming model for funding single premium deferred annuities. Technical Report 92-08-03. Philadelphia : Decision Sciences Department, The Wharton School, University of Pennsylvania .
26.
Nielsen, S.S., and Zenios, S.A.1993a. A massively parallel algorithm for nonlinear stochastic network problems. Oper. Res.41(2):319-337.
27.
Nielsen, S.S., and Zenios, S.A.1993b. Proximal minimization with D-functions and the massively parallel solution of linear network programs. Comput. Optim. Appl. 1(4):375-398.
Qi, R.J., and Zenios, S.A.1993. On the scalability of data-parallel decomposition algorithms for stochastic programs. Technical Report. Philadelphia : Decision Sciences Department, The Wharton School, University of Pennsylvania.
30.
Rockafellar, R.T.1976a. Augmented Lagrangians and applications to proximal point algorithms in convex programming. Math. Oper. Res.1:97-116.
31.
Rockafellar, R.T.1976b. Monotone operators and the proximal point algorithm . SIAM J. Control Optim.14:877-898.
32.
Rockafellar, R.T., and Wets, R.J.-B.1991. Scenarios and policy aggregation in optimization under uncertainty. Math. Oper. Res. 16(1):119-147.
33.
Ruszczynski, A.1988. Parallel decomposition of multistage stochastic programming problems.
34.
Technical Report WP-88-094. Laxenburg, Austria: International Institute for Applied Systems Analysis.
35.
Ruszczynski, A.1989. Regularized decomposition and augmented Lagrangian decomposition for angular linear programming problems. In Aspiration based decision support systems, edited by A. Levandowski and A. P. Wierzbicki.New York: Springer Verlag.
36.
Van Slyke, R., and Wets, R.J-B.1966. Programming under uncertainty and stochastic optimal control. SIAM J. Control Optim.4:179-193.
37.
Van Slyke, R., and Wets, R. J-B .1969. L-shaped linear programs with applications to optimal control and stochastic programming. SIAM J. Appl. Math.17:638-663.
38.
Wallace, S.W.1986. Solving stochastic programs with network recourse . Networks16:295-317.
39.
Wets, R. J-B.1974. Stochastic programs with fixed resources: the equivalent deterministic problem. SIAM Rev.16:309-339.
40.
Wets, R. J-B.1985. On parallel processor design for solving stochastic programs. Technical Report WP-85-67. Laxenburg, Austria: International Institute for Applied Systems Analysis .
41.
Zenios, S.A.1991. Data-level parallel computing for large scale optimization. Technical Report 91-06-02. Philadelphia: Decision Sciences Department, The Wharton School, University of Pennsylvania .
42.
Zenios, S.A., and Censor, Y.1991. Massively parallel row-action algorithms for some nonlinear transportation problems. SIAM J. Optim.1:373-400.
43.
Zenios, S.A., and Lasken, R.A.1988. Nonlinear network optimization on a massively parallel Connection Machine. Ann. Oper. Res.14:147-165.
