IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v62y2015i3p669-692.html
   My bibliography  Save this article

Scenario generation for stochastic optimization problems via the sparse grid method

Author

Listed:
  • Michael Chen
  • Sanjay Mehrotra
  • Dávid Papp

Abstract

We study the use of sparse grids in the scenario generation (or discretization) problem in stochastic programming problems where the uncertainty is modeled using a continuous multivariate distribution. We show that, under a regularity assumption on the random function involved, the sequence of optimal objective function values of the sparse grid approximations converges to the true optimal objective function values as the number of scenarios increases. The rate of convergence is also established. We treat separately the special case when the underlying distribution is an affine transform of a product of univariate distributions, and show how the sparse grid method can be adapted to the distribution by the use of quadrature formulas tailored to the distribution. We numerically compare the performance of the sparse grid method using different quadrature rules with classic quasi-Monte Carlo (QMC) methods, optimal rank-one lattice rules, and Monte Carlo (MC) scenario generation, using a series of utility maximization problems with up to 160 random variables. The results show that the sparse grid method is very efficient, especially if the integrand is sufficiently smooth. In such problems the sparse grid scenario generation method is found to need several orders of magnitude fewer scenarios than MC and QMC scenario generation to achieve the same accuracy. It is indicated that the method scales well with the dimension of the distribution—especially when the underlying distribution is an affine transform of a product of univariate distributions, in which case the method appears scalable to thousands of random variables. Copyright Springer Science+Business Media New York 2015

Suggested Citation

  • Michael Chen & Sanjay Mehrotra & Dávid Papp, 2015. "Scenario generation for stochastic optimization problems via the sparse grid method," Computational Optimization and Applications, Springer, vol. 62(3), pages 669-692, December.
    • Handle: RePEc:spr:coopap:v:62:y:2015:i:3:p:669-692
    DOI: 10.1007/s10589-015-9751-7
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10589-015-9751-7
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10589-015-9751-7?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Heiss, Florian & Winschel, Viktor, 2008. "Likelihood approximation by numerical integration on sparse grids," Journal of Econometrics, Elsevier, vol. 144(1), pages 62-80, May.
    2. M.A.H. Dempster & R.T. Thompson, 1999. "EVPI‐based importance sampling solution proceduresfor multistage stochastic linear programmeson parallel MIMD architectures," Annals of Operations Research, Springer, vol. 90(0), pages 161-184, January.
    3. Teemu Pennanen, 2005. "Epi-Convergent Discretizations of Multistage Stochastic Programs," Mathematics of Operations Research, INFORMS, vol. 30(1), pages 245-256, February.
    4. Stein W. Wallace & Stein-Erik Fleten, 2002. "Stochastic programming in energy," GE, Growth, Math methods 0201001, University Library of Munich, Germany, revised 13 Nov 2003.
    5. Jitka Dupačová & Giorgio Consigli & Stein Wallace, 2000. "Scenarios for Multistage Stochastic Programs," Annals of Operations Research, Springer, vol. 100(1), pages 25-53, December.
    6. Michael S. Casey & Suvrajeet Sen, 2005. "The Scenario Generation Algorithm for Multistage Stochastic Linear Programming," Mathematics of Operations Research, INFORMS, vol. 30(3), pages 615-631, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Zhang, Dongqing & Wallace, Stein W. & Guo, Zhaoxia & Dong, Yucheng & Kaut, Michal, 2021. "On scenario construction for stochastic shortest path problems in real road networks," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    2. Julien Keutchayan & Janosch Ortmann & Walter Rei, 2023. "Problem-driven scenario clustering in stochastic optimization," Computational Management Science, Springer, vol. 20(1), pages 1-33, December.
    3. Julien Keutchayan & Michel Gendreau & Antoine Saucier, 2017. "Quality evaluation of scenario-tree generation methods for solving stochastic programming problems," Computational Management Science, Springer, vol. 14(3), pages 333-365, July.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Rocha, Paula & Kuhn, Daniel, 2012. "Multistage stochastic portfolio optimisation in deregulated electricity markets using linear decision rules," European Journal of Operational Research, Elsevier, vol. 216(2), pages 397-408.
    2. Gah-Yi Ban & Jérémie Gallien & Adam J. Mersereau, 2019. "Dynamic Procurement of New Products with Covariate Information: The Residual Tree Method," Manufacturing & Service Operations Management, INFORMS, vol. 21(4), pages 798-815, October.
    3. D. Kuhn, 2009. "Convergent Bounds for Stochastic Programs with Expected Value Constraints," Journal of Optimization Theory and Applications, Springer, vol. 141(3), pages 597-618, June.
    4. Kostrova, Alisa & Britz, Wolfgang & Djanibekov, Utkur & Finger, Robert, 2016. "Monte-Carlo Simulation and Stochastic Programming in Real Options Valuation: the Case of Perennial Energy Crop Cultivation," Discussion Papers 250253, University of Bonn, Institute for Food and Resource Economics.
    5. Staino, Alessandro & Russo, Emilio, 2015. "A moment-matching method to generate arbitrage-free scenarios," European Journal of Operational Research, Elsevier, vol. 246(2), pages 619-630.
    6. Bakker, Hannah & Dunke, Fabian & Nickel, Stefan, 2020. "A structuring review on multi-stage optimization under uncertainty: Aligning concepts from theory and practice," Omega, Elsevier, vol. 96(C).
    7. Yonghan Feng & Sarah Ryan, 2016. "Solution sensitivity-based scenario reduction for stochastic unit commitment," Computational Management Science, Springer, vol. 13(1), pages 29-62, January.
    8. Holger Heitsch & Werner Römisch, 2009. "Scenario tree reduction for multistage stochastic programs," Computational Management Science, Springer, vol. 6(2), pages 117-133, May.
    9. Boris Defourny & Damien Ernst & Louis Wehenkel, 2013. "Scenario Trees and Policy Selection for Multistage Stochastic Programming Using Machine Learning," INFORMS Journal on Computing, INFORMS, vol. 25(3), pages 488-501, August.
    10. M. Pilar Muñoz & Cristina Corchero & F.-Javier Heredia, 2013. "Improving Electricity Market Price Forecasting with Factor Models for the Optimal Generation Bid," International Statistical Review, International Statistical Institute, vol. 81(2), pages 289-306, August.
    11. Liu, Pei-chen Barry & Hansen, Mark & Mukherjee, Avijit, 2008. "Scenario-based air traffic flow management: From theory to practice," Transportation Research Part B: Methodological, Elsevier, vol. 42(7-8), pages 685-702, August.
    12. Gulpinar, Nalan & Rustem, Berc & Settergren, Reuben, 2004. "Simulation and optimization approaches to scenario tree generation," Journal of Economic Dynamics and Control, Elsevier, vol. 28(7), pages 1291-1315, April.
    13. S. Bogan Aruoba & Pablo Cuba-Borda & Kenji Higa-Flores & Frank Schorfheide & Sergio Villalvazo, 2021. "Piecewise-Linear Approximations and Filtering for DSGE Models with Occasionally Binding Constraints," Review of Economic Dynamics, Elsevier for the Society for Economic Dynamics, vol. 41, pages 96-120, July.
    14. E. Nasakkala & J. Keppo, 2008. "Hydropower with Financial Information," Applied Mathematical Finance, Taylor & Francis Journals, vol. 15(5-6), pages 503-529.
    15. Avilés A., Camilo & Oliva H., Sebastian & Watts, David, 2019. "Single-dwelling and community renewable microgrids: Optimal sizing and energy management for new business models," Applied Energy, Elsevier, vol. 254(C).
    16. Faezeh Akhavizadegan & Lizhi Wang & James McCalley, 2020. "Scenario Selection for Iterative Stochastic Transmission Expansion Planning," Energies, MDPI, vol. 13(5), pages 1-18, March.
    17. Castro, Jordi & Escudero, Laureano F. & Monge, Juan F., 2023. "On solving large-scale multistage stochastic optimization problems with a new specialized interior-point approach," European Journal of Operational Research, Elsevier, vol. 310(1), pages 268-285.
    18. Florian Heiss, 2016. "Discrete Choice Methods with Simulation," Econometric Reviews, Taylor & Francis Journals, vol. 35(4), pages 688-692, April.
    19. Murat Köksalan & Ceren Tuncer Şakar, 2016. "An interactive approach to stochastic programming-based portfolio optimization," Annals of Operations Research, Springer, vol. 245(1), pages 47-66, October.
    20. Möst, Dominik & Keles, Dogan, 2010. "A survey of stochastic modelling approaches for liberalised electricity markets," European Journal of Operational Research, Elsevier, vol. 207(2), pages 543-556, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:coopap:v:62:y:2015:i:3:p:669-692. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.