Top > JACIII > Capacity Expansion Problem by Monte Carlo Sampling Method

single-jc.php

JACIII Vol.13 No.6 pp. 697-703
doi: 10.20965/jaciii.2009.p0697
(2009)

Paper:

Views over last 60 days: 832

Capacity Expansion Problem by Monte Carlo Sampling Method

Takayuki Shiina

Chiba Institute of Technology, 2-17-1 Tsudanuma, Narashino, Chiba 275-0016, Japan

Received:
June 25, 2008
Accepted:
March 25, 2009
Published:
November 20, 2009
Creative Commons License
Keywords:
stochastic programming with recourse, Monte Carlo method, importance sampling, capacity expansion problem.
Abstract
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.
Cite this article as:
T. Shiina, “Capacity Expansion Problem by Monte Carlo Sampling Method,” J. Adv. Comput. Intell. Intell. Inform., Vol.13 No.6, pp. 697-703, 2009.
Data files:
References
  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.

Creative Commons License  This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Jun. 12, 2025