IDEAS home Printed from https://ideas.repec.org/a/spr/comgts/v17y2020i2d10.1007_s10287-020-00375-4.html
   My bibliography  Save this article

Evaluation of scenario reduction algorithms with nested distance

Author

Listed:
  • Markéta Horejšová

    (Charles University)

  • Sebastiano Vitali

    (Charles University
    University of Bergamo)

  • Miloš Kopa

    (Charles University)

  • Vittorio Moriggia

    (University of Bergamo)

Abstract

Multistage stochastic optimization is used to solve many real-life problems where decisions are taken at multiple times. Such problems need the representation of stochastic processes, which are usually approximated by scenario trees. In this article, we implement seven scenario reduction algorithms: three based on random extraction, named Random, and four based on specific distance measures, named Distance-based. Three of the latter are well known in literature while the fourth is a new approach, namely nodal clustering. We compare all the algorithms in terms of computational cost and information cost. The computational cost is measured by the time needed for the reduction, while the information cost is measured by the nested distance between the original and the reduced tree. Moreover, we also formulate and solve a multistage stochastic portfolio selection problem to measure the distance between the optimal solutions and between the optimal objective values of the original and the reduced tree.

Suggested Citation

  • Markéta Horejšová & Sebastiano Vitali & Miloš Kopa & Vittorio Moriggia, 2020. "Evaluation of scenario reduction algorithms with nested distance," Computational Management Science, Springer, vol. 17(2), pages 241-275, June.
    • Handle: RePEc:spr:comgts:v:17:y:2020:i:2:d:10.1007_s10287-020-00375-4
    DOI: 10.1007/s10287-020-00375-4
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10287-020-00375-4
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10287-020-00375-4?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. Anna Timonina, 2015. "Multi-stage stochastic optimization: the distance between stochastic scenario processes," Computational Management Science, Springer, vol. 12(1), pages 171-195, January.
    2. Miloš Kopa & Vittorio Moriggia & Sebastiano Vitali, 2018. "Individual optimal pension allocation under stochastic dominance constraints," Annals of Operations Research, Springer, vol. 260(1), pages 255-291, January.
    3. Raimund Kovacevic & Alois Pichler, 2015. "Tree approximation for discrete time stochastic processes: a process distance approach," Annals of Operations Research, Springer, vol. 235(1), pages 395-421, December.
    4. Sebastiano Vitali & Vittorio Moriggia & Miloš Kopa, 2017. "Optimal pension fund composition for an Italian private pension plan sponsor," Computational Management Science, Springer, vol. 14(1), pages 135-160, January.
    5. Mandelli, Diego & Yilmaz, Alper & Aldemir, Tunc & Metzroth, Kyle & Denning, Richard, 2013. "Scenario clustering and dynamic probabilistic risk assessment," Reliability Engineering and System Safety, Elsevier, vol. 115(C), pages 146-160.
    6. Soňa Kilianová & Georg Pflug, 2009. "Optimal pension fund management under multi-period risk minimization," Annals of Operations Research, Springer, vol. 166(1), pages 261-270, February.
    7. Moriggia, Vittorio & Kopa, Miloš & Vitali, Sebastiano, 2019. "Pension fund management with hedging derivatives, stochastic dominance and nodal contamination," Omega, Elsevier, vol. 87(C), pages 127-141.
    8. Rockafellar, R. Tyrrell & Uryasev, Stanislav, 2002. "Conditional value-at-risk for general loss distributions," Journal of Banking & Finance, Elsevier, vol. 26(7), pages 1443-1471, July.
    9. Holger Heitsch & Werner Römisch, 2009. "Scenario tree reduction for multistage stochastic programs," Computational Management Science, Springer, vol. 6(2), pages 117-133, May.
    10. Patrizia Beraldi & Maria Bruni, 2014. "A clustering approach for scenario tree reduction: an application to a stochastic programming portfolio optimization problem," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 22(3), pages 934-949, October.
    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. Alois Pichler & Michael Weinhardt, 2022. "The nested Sinkhorn divergence to learn the nested distance," Computational Management Science, Springer, vol. 19(2), pages 269-293, June.
    2. Li, Wei & Paraschiv, Florentina, 2022. "Modelling the evolution of wind and solar power infeed forecasts," Journal of Commodity Markets, Elsevier, vol. 25(C).
    3. Alkhaleel, Basem A. & Liao, Haitao & Sullivan, Kelly M., 2022. "Risk and resilience-based optimal post-disruption restoration for critical infrastructures under uncertainty," European Journal of Operational Research, Elsevier, vol. 296(1), pages 174-202.

    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. Miloš Kopa & Tomáš Rusý, 2021. "A decision-dependent randomness stochastic program for asset–liability management model with a pricing decision," Annals of Operations Research, Springer, vol. 299(1), pages 241-271, April.
    2. Martin Glanzer & Georg Ch. Pflug, 2020. "Multiscale stochastic optimization: modeling aspects and scenario generation," Computational Optimization and Applications, Springer, vol. 75(1), pages 1-34, January.
    3. Sebastiano Vitali & Vittorio Moriggia, 2021. "Pension fund management with investment certificates and stochastic dominance," Annals of Operations Research, Springer, vol. 299(1), pages 273-292, April.
    4. František Zapletal & Martin Šmíd & Miloš Kopa, 2020. "Multi-stage emissions management of a steel company," Annals of Operations Research, Springer, vol. 292(2), pages 735-751, September.
    5. Sebastiano Vitali & Ruth Domínguez & Vittorio Moriggia, 2021. "Comparing stage-scenario with nodal formulation for multistage stochastic problems," 4OR, Springer, vol. 19(4), pages 613-631, December.
    6. Justo Puerto & Moises Rodr'iguez-Madrena & Andrea Scozzari, 2019. "Location and portfolio selection problems: A unified framework," Papers 1907.07101, arXiv.org.
    7. Giorgio Consigli & Vittorio Moriggia & Sebastiano Vitali, 2020. "Long-term individual financial planning under stochastic dominance constraints," Annals of Operations Research, Springer, vol. 292(2), pages 973-1000, September.
    8. Yu Mei & Zhiping Chen & Jia Liu & Bingbing Ji, 2022. "Multi-stage portfolio selection problem with dynamic stochastic dominance constraints," Journal of Global Optimization, Springer, vol. 83(3), pages 585-613, July.
    9. Jitka Dupačová & Václav Kozmík, 2017. "SDDP for multistage stochastic programs: preprocessing via scenario reduction," Computational Management Science, Springer, vol. 14(1), pages 67-80, January.
    10. Libo Yin & Liyan Han, 2013. "Options strategies for international portfolios with overall risk management via multi-stage stochastic programming," Annals of Operations Research, Springer, vol. 206(1), pages 557-576, July.
    11. Jia Liu & Zhiping Chen & Giorgio Consigli, 2021. "Interval-based stochastic dominance: theoretical framework and application to portfolio choices," Annals of Operations Research, Springer, vol. 307(1), pages 329-361, December.
    12. Jitka Dupačová & Miloš Kopa, 2012. "Robustness in stochastic programs with risk constraints," Annals of Operations Research, Springer, vol. 200(1), pages 55-74, November.
    13. Weiguo Zhang & Xiaolei He, 2022. "A New Scenario Reduction Method Based on Higher-Order Moments," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 1903-1918, July.
    14. Homem-de-Mello, Tito & Pagnoncelli, Bernardo K., 2016. "Risk aversion in multistage stochastic programming: A modeling and algorithmic perspective," European Journal of Operational Research, Elsevier, vol. 249(1), pages 188-199.
    15. Domínguez, Ruth & Vitali, Sebastiano & Carrión, Miguel & Moriggia, Vittorio, 2021. "Analysing decarbonizing strategies in the European power system applying stochastic dominance constraints," Energy Economics, Elsevier, vol. 101(C).
    16. Miloš Kopa & Vittorio Moriggia & Sebastiano Vitali, 2018. "Individual optimal pension allocation under stochastic dominance constraints," Annals of Operations Research, Springer, vol. 260(1), pages 255-291, January.
    17. Mínguez, R. & van Ackooij, W. & García-Bertrand, R., 2021. "Constraint generation for risk averse two-stage stochastic programs," European Journal of Operational Research, Elsevier, vol. 288(1), pages 194-206.
    18. Sebastiano Vitali & Vittorio Moriggia & Miloš Kopa, 2017. "Optimal pension fund composition for an Italian private pension plan sponsor," Computational Management Science, Springer, vol. 14(1), pages 135-160, January.
    19. Michal Mešťan & Ivan Králik & Matej Žofaj & Nikola Karkošiaková & Audrius Kabašinskas, 2021. "Projections of pension benefits in supplementary pension saving scheme in Slovakia," Central European Journal of Operations Research, Springer;Slovak Society for Operations Research;Hungarian Operational Research Society;Czech Society for Operations Research;Österr. Gesellschaft für Operations Research (ÖGOR);Slovenian Society Informatika - Section for Operational Research;Croatian Operational Research Society, vol. 29(2), pages 687-712, June.
    20. Moriggia, Vittorio & Kopa, Miloš & Vitali, Sebastiano, 2019. "Pension fund management with hedging derivatives, stochastic dominance and nodal contamination," Omega, Elsevier, vol. 87(C), pages 127-141.

    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:comgts:v:17:y:2020:i:2:d:10.1007_s10287-020-00375-4. 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.