Skip to main content
Springer Nature Link
Log in

Quality evaluation of scenario-tree generation methods for solving stochastic programming problems

  • Original Paper
  • Published:
Computational Management Science Aims and scope Submit manuscript

Abstract

This paper addresses the generation of scenario trees to solve stochastic programming problems that have a large number of possible values for the random parameters (possibly infinitely many). For the sake of the computational efficiency, the scenario trees must include only a finite (rather small) number of scenarios, therefore, they provide decisions only for some values of the random parameters. To overcome the resulting loss of information, we propose to introduce an extension procedure. It is a systematic approach to interpolate and extrapolate the scenario-tree decisions to obtain a decision policy that can be implemented for any value of the random parameters at little computational cost. To assess the quality of the scenario-tree generation method and the extension procedure (STGM-EP), we introduce three generic quality parameters that focus on the quality of the decisions. We use these quality parameters to develop a framework that will help the decision-maker to select the most suitable STGM-EP for a given stochastic programming problem. We perform numerical experiments on two case studies. The quality parameters are used to compare three scenario-tree generation methods and three extension procedures (hence nine couples STGM-EP). We show that it is possible to single out the best couple in both problems, which provides decisions close to optimality at little computational cost.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+
from €37.37 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Price includes VAT (Norway)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

References

  • Bayraksan G, Morton DP (2009) Assessing solution quality in stochastic programs via sampling. In: Oskoorouchi MR, Gray P, Greenberg HJ (eds) Tutorials in operations research: Decision technologies and applications. Informs, pp 102 –122

  • Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust optimization. Princeton University Press, Princeton

    Book  Google Scholar 

  • Birge JR, Louveaux F (1997) Introduction to stochastic programming. Springer, New York

    Google Scholar 

  • Chen M, Mehrotra S (2008) Epi-convergent scenario generation method for stochastic problems via sparse grid. Stoch Program E-Print Ser 7

  • Chen M, Mehrotra S, Papp D (2015) Scenario generation for stochastic optimization problems via the sparse grid method. Comput Optim Appl 62(3):669–692

    Article  Google Scholar 

  • Chiralaksanakul A, Morton DP (2004) Assessing policy quality in multi-stage stochastic programming. Stoch Program E-Print Ser (12)

  • Defourny B, Ernst D, Wehenkel L (2011) Multistage stochastic programming: a scenario tree based approach. In: Sucar LE, Morales EF, Hoey J (eds) Decision theory models for applications in artificial intelligence: concepts and solutions. IGI Global, pp 97–143

  • Defourny B, Ernst D, Wehenkel L (2013) Scenario trees and policy selection for multistage stochastic programming using machine learning. INFORMS J Comput 25(3):488–501

    Article  Google Scholar 

  • Drew SS, Homem-de Mello T (2006) Quasi-Monte Carlo strategies for stochastic optimization. In: Proceedings of the 38th conference on Winter simulation. Winter Simulation Conference, pp 774–782

  • Dupačová J, Gröwe-Kuska N, Römisch W (2003) Scenario reduction in stochastic programming. Math Program 95(3):493–511

    Article  Google Scholar 

  • Dyer M, Stougie L (2006) Computational complexity of stochastic programming problems. Math Program 106(3):423–432

    Article  Google Scholar 

  • Edirisinghe N (1999) Bound-based approximations in multistage stochastic programming: nonanticipativity aggregation. Ann Oper Res 85:103–127

    Article  Google Scholar 

  • Frauendorfer K (1996) Barycentric scenario trees in convex multistage stochastic programming. Math Program 75(2):277–293

    Article  Google Scholar 

  • Hanasusanto GA, Kuhn D, Wiesemann W (2016) A comment on computational complexity of stochastic programming problems. Math Program 159(1):557–569

    Article  Google Scholar 

  • Heitsch H, Römisch W (2009) Scenario tree modeling for multistage stochastic programs. Math Program 118(2):371–406

    Article  Google Scholar 

  • Hilli P, Pennanen T (2008) Numerical study of discretizations of multistage stochastic programs. Kybernetika 44(2):185–204

    Google Scholar 

  • Høyland K, Kaut M, Wallace SW (2003) A heuristic for moment-matching scenario generation. Comput Optim Appl 24(2–3):169–185

    Article  Google Scholar 

  • Høyland K, Wallace SW (2001) Generating scenario trees for multistage decision problems. Manag Sci 47(2):295–307

    Article  Google Scholar 

  • Kaut M, Wallace SW (2007) Evaluation of scenario-generation methods for stochastic programming. Pac J Optim 3(2):257–271

    Google Scholar 

  • Koivu M (2005) Variance reduction in sample approximations of stochastic programs. Math Program 103(3):463–485

    Article  Google Scholar 

  • Kouwenberg R (2001) Scenario generation and stochastic programming models for asset liability management. Eur J Oper Res 134(2):279–292

    Article  Google Scholar 

  • Küchler C, Vigerske S (2010) Numerical evaluation of approximation methods in stochastic programming. Optimization 59(3):401–415

    Article  Google Scholar 

  • L’Ecuyer P, Lemieux C (2000) Variance reduction via lattice rules. Manag Sci 46(9):1214–1235

    Article  Google Scholar 

  • Leövey H, Römisch W (2015) Quasi-Monte Carlo methods for linear two-stage stochastic programming problems. Math Program 151(1):315–345

    Article  Google Scholar 

  • Louveaux F (1998) An introduction to stochastic transportation models. In: Labbé M, Laporte G, Tanczos K, Toint P (eds) Operations research and decision aid methodologies in traffic and transportation management. Springer, Berlin, pp 244 –263

  • Mak W-K, Morton DP, Wood RK (1999) Monte carlo bounding techniques for determining solution quality in stochastic programs. Oper Res Lett 24(1):47–56

    Article  Google Scholar 

  • Pennanen T (2005) Epi-convergent discretizations of multistage stochastic programs. Math Oper Res 30(1):245–256

    Article  Google Scholar 

  • Pennanen T, Koivu M (2002) Integration quadratures in discretization of stochastic programs. Stoch Program E-Print Ser 11

  • Pflug GC (2001) Scenario tree generation for multiperiod financial optimization by optimal discretization. Math Program 89(2):251–271

    Article  Google Scholar 

  • Pflug GC, Pichler A (2012) A distance for multistage stochastic optimization models. SIAM J Optim 22(1):1–23

    Article  Google Scholar 

  • Pflug GC, Pichler A (2015) Dynamic generation of scenario trees. Comput Optim Appl 62(3):641–668

    Article  Google Scholar 

  • Powell WB, Topaloglu H (2003) Stochastic programming in transportation and logistics. In: Ruszczyński A, Shapiro A (eds) Handbooks in operations research and management science: stochastic programming, vol 10. Elsevier, Amsterdam, pp 555–635

    Google Scholar 

  • Proulx S (2014) Génération de scénarios par quantification optimale en dimension élevée. Master’s thesis, École Polytechnique de Montréal

  • Rockafellar RT, Wets RJ (1974) Continuous versus measurable recourse in n-stage stochastic programming. J Math Anal Appl 48(3):836–859

    Article  Google Scholar 

  • Ruszczyński A, Shapiro A (2003) Stochastic programming models. In: Ruszczyński A, Shapiro A (eds) Handbooks in operations research and management science: stochastic Programming, vol 10. Elsevier, Amsterdam, pp 1–64

    Google Scholar 

  • Schultz R (2003) Stochastic programming with integer variables. Math Program 97(1):285–309

    Article  Google Scholar 

  • Schultz R, Nowak MP, Nürnberg R, Römisch W, Westphalen M (2003) Stochastic programming for power production and trading under uncertainty. Mathematics key technology for the future. Springer, Berlin, pp 623–636

    Chapter  Google Scholar 

  • Shapiro A (2003) Monte Carlo sampling methods. In: Ruszczyński A, Shapiro A (eds) Handbooks in operations research and management science: stochastic Programming, vol 10. Elsevier, Amsterdam, pp 353–425

    Google Scholar 

  • Shapiro A, Homem-de Mello T (1998) A simulation-based approach to two-stage stochastic programming with recourse. Math Program 81(3):301–325

    Article  Google Scholar 

  • Sloan IH, Kuo FY, Joe S (2002) Constructing randomly shifted lattice rules in weighted sobolev spaces. SIAM J Numer Anal 40(5):1650–1665

    Article  Google Scholar 

  • Wallace SW, Fleten S-E (2003) Stochastic programming models in energy. In: Ruszczyński A, Shapiro A (eds) Handbooks in operations research and management science: stochastic Programming, vol 10. Elsevier, Amsterdam, pp 637–677

    Google Scholar 

  • Yu L-Y, Ji X-D, Wang S-Y (2003) Stochastic programming models in financial optimization: a survey. Adv Model Optim 5(1):1–26

Download references

Acknowledgements

This work was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) under Grants RGPIN-2015-04696 and PIN-115965. This support is gratefully acknowledged.

Author information

Authors and Affiliations

  1. Department of Mathematics and Industrial Engineering, École Polytechnique de Montréal, Montreal, Canada

    Julien Keutchayan, Michel Gendreau & Antoine Saucier

  2. Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Montreal, Canada

    Julien Keutchayan & Michel Gendreau

Authors
  1. Julien Keutchayan
    View author publications

    Search author on:PubMed Google Scholar

  2. Michel Gendreau
    View author publications

    Search author on:PubMed Google Scholar

  3. Antoine Saucier
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to Julien Keutchayan.

Appendix: Notation

Appendix: Notation

Notation

Description

T

Optimization horizon

\(\varvec{\xi }_t\)

Random vector at stage t

\(\varvec{\xi }\) or \((\varvec{\xi }_1,\ldots ,\varvec{\xi }_T)\)

Stochastic process

\(\varvec{\xi }_{..t}\)

Components from stage 0 to stage t of \(\varvec{\xi }\)

\(\xi _t\) (resp. \(\xi \); resp. \(\xi _{..t}\))

A realization of \(\varvec{\xi }_t\) (resp. \(\varvec{\xi }\); resp. \(\varvec{\xi }_{..t}\))

\(\varXi _t\) (resp. \(\varXi \); resp. \(\varXi _{..t}\))

Support of \(\varvec{\xi }_t\) (resp. \(\varvec{\xi }\); resp. \(\varvec{\xi }_{..t}\))

d

Number of random parameters revealed at each period

s

Number of decisions made at each stage

\(q(\cdot ; \cdot )\)

Revenue function

\(Q(\cdot )\)

Expected revenue function

\(Q(x^*)\)

Optimal value of the stochastic program

\(x_t\)

Decision function if \(t \ge 1\); decision vector if \(t = 0\)

x or \((x_0,\ldots ,x_T)\)

Decision policy

\(x_{..t}\)

Components from stage 0 to stage t of x

\(x^*\)

Optimal policy of the stochastic program

\(X_t\)

Feasible decision set at stage t

\(\widetilde{x}\)

Extended decision policy

\(\overline{x}\)

Feasible extended decision policy

\(\mathcal {N}\)

Node set of the scenario tree

\(\mathcal {E}\)

Edge set of the scenario tree

\(\mathcal {N}^*\)

Set of nodes minus the root

\(\mathcal {N}_t\)

Node set at stage t

\(n_0\)

Root node

a(n)

Ancestor node of n

C(n)

Set of children nodes of n

\(\zeta ^n\)

Discretization vector at node n

\(\zeta ^{..n}\)

Discretization sequence leading to node n

\(w^n\)

Weight of node n with respect to its siblings

\(W^n\)

Weight of node n with respect to the whole scenario tree

\(\widehat{Q}^*\)

Optimal value of a deterministic program

\(\widehat{x}^n\)

Decision vector at node n

\(\widehat{x}^{..n}\)

Sequence of decision vectors leading to node n

\(\widehat{x}^{*n}\)

Optimal decision vector at node n

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Keutchayan, J., Gendreau, M. & Saucier, A. Quality evaluation of scenario-tree generation methods for solving stochastic programming problems. Comput Manag Sci 14, 333–365 (2017). https://doi.org/10.1007/s10287-017-0279-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue date:

  • DOI: https://doi.org/10.1007/s10287-017-0279-4

Keywords