We consider the stochastic programming problem with recourse in which the expectation of the recourse function requires a large number of function evaluations, and its application to the capacity expansion problem. We propose an algorithm which combines an L-shaped method and a Monte Carlo method. The importance sampling technique is applied to obtain variance reduction. In the previous approach, the recourse function is approximated as an additive form in which the function is separable in the components of the stochastic vector. In our approach, the approximate additive form of the recourse function is perturbed to define the new density function. Numerical results for the capacity expansion problem are presented.

1. [1] J. R. Birge and F. Louveaux, “Introduction to Stochastic Programming,” Springer-Verlag, 1997.
2. [2] T. Shiina, “Stochastic programming,” In: M. Kubo, A. Tamura, and T. Matsui (Eds.), Ôyô Sûri-Keikaku Handbook, Asakura Syoten, Tokyo, pp. 710-769, 2002 (in Japanese).
3. [3] J. R. Birge, “Stochastic programming computation and applications,” INFORMS Journal on Computing, 9, pp. 111-133, 1997.
4. [4] R. Van Slyke and R. J.-B. Wets, “L-shaped linear programs with applications to optimal control and stochastic linear programs,” SIAM Journal on Applied Mathematics, 17, pp. 638-663, 1969.
5. [5] J. F. Benders, “Partitioning procedures for solving mixed variables programming problems,” Numerische Mathematik, 4, pp. 238-252, 1962.
6. [6] T. Shiina, “L-shaped decomposition method for multi-stage stochastic concentrator location problem,” Journal of the Operations Research Society of Japan, 43, pp. 317-332, 2000.
7. [7] T. Shiina, “Stochastic programming model for the design of computer network,” Transactions of the Japan Society for Industrial and Applied Mathematics, 10, pp. 37-50, 2000 (in Japanese).
8. [8] T. Shiina and J. R. Birge, “Multi-stage stochastic programming model for electric power capacity expansion problem,” Japan Journal of Industrial and Applied Mathematics, 20, pp. 379-397, 2003.
9. [9] J. M. Hammersly and D. C. Handscomb, “Monte Carlo Methods,” Mathuen, 1964.
10. [10] S. Morito and H. Sakasegawa, “System Simulation,” Asakura Syoten, 2000 (in Japanese).
11. [11] H. Sakasegawa, “Rare event simulation techniques for queueing models,” Ôyô Sûri (Bulletin of the Japan Society for Industrial and Applied Mathematics), 9, pp. 124-134, 1999 (in Japanese).
12. [12] J. L. Higle and S. Sen, “Stochastic decomposition: an algorithm for two stage stochastic linear programs with recourse,” Mathematics of Operations Research, 16, pp. 650-669, 1991.
13. [13] J. L. Higle and S. Sen, “Statistical verification of optimality conditions for stochastic programs with recourse,” Annals of Operations Research, 30, pp. 215-240, 1991.
14. [14] J. L. Higle and S. Sen, “Stochastic decomposition,” Kluwer Academic Publishers, 1996.
15. [15] G. B. Dantzig and P. Glynn, “Parallel processors for planning under uncertainty,” Annals of Operations Research, 22, pp. 1-21, 1990.
16. [16] G. B. Dantzig and G. Infanger, “Large-scale stochastic linear programs -importance sampling and Benders decomposition-,” Computational and applied Mathematics I, C. Brezinski and U. Kulish (Eds.), Elsevier Science Publishers B. V., pp. 111-120, 1997.
17. [17] G. B. Dantzig and G. Infanger, “Intelligent control and optimization under uncertainty with application to hydro power,” European Journal of Operational Research, 97, pp. 396-407, 1997.
18. [18] G. Infanger, “Monte Carlo (importance) sampling within a Benders decomposition algorithm for stochastic linear programs,” Annals of Operations Research, 39, pp. 65-95, 1992.
19. [19] G. Infanger, “Planning under Uncertainty,” Boyd and Fraser, 1993.
20. [20] R. Fourer, D. M. Gay, and B. W. Kernighan, “AMPL: A Modeling Language for Mathematical Programming,” Scientific Press, 1993.