Monte Carlo (importance) sampling within a Benders decomposition algorithm for stochastic linear programs.

*(English)*Zbl 0773.90054Summary: This paper focuses on Benders decomposition techniques and Monte Carlo sampling (importance sampling) for solving two-stage stochastic linear programs with recourse, a method first introduced by G. B. Dantzig and P. W. Glym [Ann. Oper. Res. 22, 1-21 (1990; Zbl 0714.90074)]. The algorithm is discussed and further developed. The paper gives a complete presentation of the method as it is currently implemented. Numerical results from test problems of different areas are presented. Using small test problems, we compare the solutions obtained by the algorithm with universe solutions. We present the solutions of large- scale problems with numerous stochastic parameters, which in the deterministic formulation would have billions of constraints. The problems concern expansion planning of electric utilities with uncertainty in the availabilities of generators and transmission lines and portfolio management with uncertainty in the future returns.

##### MSC:

90C15 | Stochastic programming |

90C90 | Applications of mathematical programming |

90B90 | Case-oriented studies in operations research |

90-08 | Computational methods for problems pertaining to operations research and mathematical programming |

##### Keywords:

Benders decomposition techniques; Monte Carlo sampling; two-stage stochastic linear programs with recourse; large-scale problems with numerous stochastic parameters; expansion planning of electric utilities; portfolio management##### Software:

MINOS
Full Text:
DOI

**OpenURL**

##### References:

[1] | M. Avriel, G.B. Dantzig and P.W. Glynn, Decomposition and parallel processing techniques for large scale electric power system planning under uncertainty,Proc. Workshop on Resource Planning Under Uncertainty, Stanford University (1989). |

[2] | J.F. Benders, Partitioning procedures for solving mixed-variable programming problems, Numer. Math. 4(1962)238–252. · Zbl 0109.38302 |

[3] | J.R. Birge, Decomposition and partitioning methods for multi-stage stochastic linear programming, Oper. Res. 33(1985)989–1007. · Zbl 0581.90065 |

[4] | J.R. Birge and S.W. Wallace, A separable piecewise linear upper bound for stochastic linear programs, SIAM J. Control Optim. 26(1988)3. · Zbl 0646.90064 |

[5] | J.R. Birge and R.J. Wets, Designing approximation schemes for stochastic optimization problems, in particular for stochastic programs with recourse, Math. Progr. Study 27(1986)54–102. · Zbl 0603.90104 |

[6] | G.B. Dantzig, Linear programming under uncertainty, Manag. Sci. 1(1955)197–206. · Zbl 0995.90589 |

[7] | G.B. Dantzig and P.W. Glynn, Parallel processors for planning under uncertainty, Ann. Oper. Res. 22(1990)1–21. · Zbl 0714.90074 |

[8] | G.B. Dantzig, P.W. Glynn, M. Avriel, J. Stone, R. Entriken and M. Nakayama, Decomposition techniques for multi-area generation and transmission planning under uncertainty, EPRI Report 2940-1 (1989). |

[9] | P.J. Davis and P. Rabinowitz,Methods of Numerical Integration (Academic Press, London, 1984). · Zbl 0537.65020 |

[10] | Y. Ermoliev, Stochastic quasi-gradient methods and their applications to systems optimization, Stochastics 9(1983)1–36. · Zbl 0512.90079 |

[11] | Y. Ermoliev and R.J. Wets (eds.),Numerical Techniques for Stochastic Optimization (Springer, 1988). · Zbl 0658.00020 |

[12] | K. Frauendorfer, Solving SLP recourse problems with arbitrary multivariate distributions – the dependent case, Math. Oper. Res. 13(1988)377–394. · Zbl 0652.90080 |

[13] | K. Frauendorfer and P. Kall, Solving SLP recourse problems with arbitrary multivariate distributions – the independent case, Probl. Control Inf. Theory 17(1988)177–205. · Zbl 0651.90054 |

[14] | A.M. Geoffrion, Elements of large-scale mathematical programming, Manag. Sci. 16, no. 11 (1974). · Zbl 0395.90056 |

[15] | P.W. Glynn and D.L. Iglehart, Importance sampling for stochastic simulation, Manag. Sci. 35(1989)1367–1392. · Zbl 0691.65107 |

[16] | J.M. Hammersly and D.C. Handscomb,Monte Carlo Methods (Methuen, London, 1964). · Zbl 0121.35503 |

[17] | P. Hall, Rates of convergence in the central limit theorem, Res. Notes Math. 62 (1982). · Zbl 0497.60001 |

[18] | J.L. Higle and S. Sen, Stochastic decomposition: An algorithm for two stage linear programs with recourse, Math. Oper. Res. (1989), to appear. · Zbl 0746.90045 |

[19] | J.L. Higle, S. Sen and D. Yakowitz, Finite master programs in stochastic decomposition, Technical Report, Department of Systems and Industrial Engineering, University of Arozina, Tucson, AZ 85721. · Zbl 0828.90097 |

[20] | P. Kall, Computational methods for two stage stochastic linear programming problems, Z. angew. Math. Phys. 30(1979)261–271. · Zbl 0411.90056 |

[21] | P. Kall, A. Ruszczynski and K. Frauendorfer, Approximation techniques in stochastic programming, in:Numerical Techniques for Stochastic Optimization, ed. Y. Ermoliev and R.J. Wets (1988). · Zbl 0665.90067 |

[22] | F.V. Louveaux and Y. Smeers, Optimal investment for electricity generation: A stochastic model and a test problem, in:Numerical Techniques for Stochastic Optimization, ed. Y. Ermoliev and R.J. Wets (1988). · Zbl 0659.90061 |

[23] | J.M. Mulvey and H. Vladimirou, Specifying the progressive hedging algorithm to stochastic generalized networks, Sstatistics and Operations Research Series Report SOR-89-9, Princeton University, Princeton, NJ 08544 (1989). |

[24] | B.A. Murtagh and M.A. Saunders, MINOS user’s guide, SOL 82-20, Department of Operations Research, Stanford University, Stanford, CA 94305 (1983). |

[25] | L. Nazareth and R.J. Wets, Algorithms for stochastic programs: The case of nonstochastic tenders, Math. Progr. Study 28(1987)48–62. · Zbl 0605.90093 |

[26] | M.V. Pereira, L.M.V.G. Pinto, G.C. Oliveira and S.H.F. Cunha, A technique for solving LP-problems with stochastic right-hand sides, CEPEL, Centro del Pesquisas de Energia Electria, Rio de Janeiro, Brazil (1989). |

[27] | R.T. Rockafellar and R.J. Wets, Scenario and policy aggregation in optimization under uncertainty, Math. Oper. Res. (1989), to appear. |

[28] | A. Ruszczynski, A regularized decomposition method for minimizing a sum of polyhedral functions, Math. Progr. 35(1986)309–333. · Zbl 0599.90103 |

[29] | R.M. Van Slyke and R.J. Wets, L-shaped linear programs with applications to optimal control and stochastic programming, SIAM J. Appl. Math. 17(1969)638–663. · Zbl 0197.45602 |

[30] | R.J. Wets, Programming under uncertainty: The equivalent convex program, SIAM J. Appl. Math. 14(1984)89–105. · Zbl 0139.13303 |

[31] | J. Tomlin, LPM1 user’s guide, Manuscript, Systems Optimization Laboratory, Stanford University (1973), unpublished. |

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.