zbMATH — the first resource for mathematics

MSLiP: A computer code for the multistage stochastic linear programming problem. (English) Zbl 0701.90070
Summary: This paper describes an efficient implementation of a nested decomposition algorithm for the multistage stochastic linear programming problem. Many of the computational tricks developed for deterministic staircase problems are adapted to the stochastic setting and their effect on computation times is investigated. The computer code supports an arbitrary number of time periods and various types of random structures for the input data. Numerical results compare the performance of the algorithm to MINOS 5.0.

90C15 Stochastic programming
90C05 Linear programming
65K05 Numerical mathematical programming methods
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text: DOI
[1] P.G. Abrahamson, ”A nested decomposition approach for solving staircase linear programs,” Technical Report SOL 83-4, Systems Optimization Laboratory, Stanford University (Stanford, CA, 1983). · Zbl 0538.90052
[2] J.F. Benders, ”Partitioning procedures for solving mixed-variables programming problems,”Numerische Mathematik 4 (1962) 238–252. · Zbl 0109.38302 · doi:10.1007/BF01386316
[3] J.R. Birge, ”Solution methods for stochastic dynamic linear programs,” Technical Report SOL 80-29, Systems Optimization Laboratory, Stanford University (Stanford, CA, 1980).
[4] J.R. Birge, ”Decomposition and partitioning methods for multistage stochastic linear programs,”Operations Research 33 (1985) 989–1007. · Zbl 0581.90065 · doi:10.1287/opre.33.5.989
[5] J.R. Birge, ”NDSP User’s manual,” in: J. Edwards, ed.,Documentation for the ADO/SDS collection of stochastic programming codes, Working Paper WP-85-02, International Institute for Applied Systems Analysis (Laxenburg, Austria, 1985).
[6] J.R. Birge, M.A.H. Dempster, H.I. Gassmann, E.A. Gunn, A.J. King and S.W. Wallace, ”A standard input format for multiperiod stochastic linear programs,”COAL Newsletter 17 (1987) 1–20.
[7] J.R. Birge and F.V. Louveaux, ”A multicut algorithm for two-stage linear programs,”European Journal of Operational Research 34 (1988) 384–392. · Zbl 0647.90066 · doi:10.1016/0377-2217(88)90159-2
[8] P. Birge, ”A research bibliography in stochastic programming,” Working Paper, International Institute for Applied Systems Analysis (Laxenburg, Austria, 1988).
[9] J. Bisschop and A. Meeraus, ”Matrix augmentation and partitioning in the updating of the basis inverse,”Mathematical Programming 13 (1977) 241–254. · Zbl 0372.90083 · doi:10.1007/BF01584341
[10] S.P. Bradley and D.B. Crane, ”A dynamic model for bond portfolio management,”Management Science 19 (1972) 139–151. · doi:10.1287/mnsc.19.2.139
[11] V. Chvatál,Linear Programming (Freeman, New York, 1983).
[12] G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, Princeton, NJ, 1963).
[13] G.B. Dantzig and P. Wolfe, ”Decomposition principle for linear programs,”Operations Research 8 (1960), 101–111. · Zbl 0093.32806 · doi:10.1287/opre.8.1.101
[14] H.I. Gassmann, ”Optimal harvest of a forest in the presence of uncertainty,”Canadian Journal of Forest Research 19 (1989) 1267–1274.
[15] S. Garstka and D. Rutenberg, ”Computation in discrete stochastic programs with recourse,”Operations Research 21 (1973) 112–122. · Zbl 0267.90072 · doi:10.1287/opre.21.1.112
[16] C.R. Glassey, ”Nested decomposition and multi-stage linear programs,”Management Science 20 (1973) 282–292. · Zbl 0313.90037 · doi:10.1287/mnsc.20.3.282
[17] D. Haugland and S.W. Wallace, ”Solving many linear programs that differ only in the righthand side,” Working Paper #372102-1, Christian Michelsen Institute (Bergen, Norway, 1986).
[18] J.K. Ho, ”Convergence behavior of decomposition algorithms for linear programs,”Operations Research Letters 2 (1984) 91–94. · Zbl 0547.90067 · doi:10.1016/0167-6377(84)90048-8
[19] J.K. Ho and E. Loute, ”A set of staircase linear programming test problems,”Mathematical Programming 20 (1981) 245–250. · Zbl 0448.90036 · doi:10.1007/BF01589349
[20] J.K. Ho and A.S. Manne, ”Nested decomposition for dynamic models,”Mathematical Programming 6 (1974) 121–140. · Zbl 0294.90051 · doi:10.1007/BF01580231
[21] J.G. Kallberg and W.T. Ziemba, ”An algorithm for portfolio revision: Theory, Computational Algorithm and empirical results,” in: R.A. Schultz, ed.,Applications of Management Science, Vol. I (JAI Press, Greenwich, CT, 1981) pp. 267–292. · Zbl 0534.90006
[22] F.V. Louveaux, ”A solution method for multistage stochastic programs with application to an energy investment problem,”Operations Research 28 (1980) 889–902. · Zbl 0441.90076 · doi:10.1287/opre.28.4.889
[23] R.R. Merkovsky, ”Near-linear convergent procedures for convex and large scale optimization based on linear programming: Theory and Applications,” Ph.D. Thesis, Dalhousie University (Halifax, N.S., 1987).
[24] F. Mirzoakhmedov and M.V. Mikhalevich, ”Modelling of optimal cultivated land distribution by means of a multistage stochastic programming problem,”Ekonomicheski i matematicheskie metody 18 (1982) 918–922 (in Russian).
[25] B.A. Murtagh and M.A. Saunders, ”MINOS 5.0 user’s guide,” Technical Report SOL 83-20, Systems Optimization Laboratory, Stanford University (Stanford, CA, 1983).
[26] M.-C. Noël and Y. Smeers, ”Nested decomposition of multistage nonlinear programs with recourse,” CORE Working Paper #8505, Université Catholique de Louvain (Louvain-la-Neuve, Belgium, 1985). · Zbl 0619.90054
[27] R.P. O’Neill, ”Nested decomposition of multistage convex programs,”SIAM Journal of Control and Optimization 14 (1976) 409–418. · Zbl 0333.90039 · doi:10.1137/0314027
[28] C.E. Pfefferkorn and J.A. Tomlin, ”Design of a linear programming system for ILLIAC IV,” Technical Report SOL 76-8, Systems Optimization Laboratory, Stanford University (Stanford, CA,. 1976).
[29] A.N. Rae, ”Stochastic programming, utility and sequential decision problems in farm management,”American Journal of Agricultural Economics 53 (1971) 625–638. · doi:10.2307/1237827
[30] R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, NJ, 1970). · Zbl 0193.18401
[31] D.M. Scott, ”A dynamic programming approach to time staged convex programs,” Technical Report SOL 85-3, Systems Optimization Laboratory, Stanford University (Stanford, CA, 1985).
[32] S.B. Smith, ”Planning transistor production by linear programming,”Operations Research 13 (1965) 132–139. · doi:10.1287/opre.13.1.132
[33] R. Van Slyke and R.J.-B. Wets, ”L-shaped linear programs with application to optimal control and stochastic optimization,”SIAM Journal on Applied Mathematics 17 (1969) 638–663. · Zbl 0197.45602 · doi:10.1137/0117061
[34] D. Walkup and R.J.-B. Wets, ”Lifting projections of convex polyhedra,”Pacific Journal of Mathematics 28 (1969) 465–475. · Zbl 0172.23702
[35] R.J.-B. Wets, ”Large scale linear programming techniques in stochastic programming,” in: Yu. Ermoliev and R.J.-B. Wets, eds.,Numerical Methods in Stochastic Optimization, Lecture Notes in Mathematics (Springer, Berlin, 1988). · Zbl 0676.90043
[36] R.J. Wittrock, ”Advances in a nested decomposition algorithm for solving staircase linear programs,” Technical Report SOL 83-2, Systems Optimization Laboratory, Stanford University (Stanford, CA, 1983).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.