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

被引：7
作者：
Keutchayan J. [1 ,2 ]
Gendreau M. [1 ,2 ]
Saucier A. [1 ]
机构：
[1] Department of Mathematics and Industrial Engineering, École Polytechnique de Montréal, Montreal
[2] Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT), Montreal
来源：
Computational Management Science | 2017年 / 14卷 / 3期
基金：
加拿大自然科学与工程研究理事会;
关键词：
Decision policy; Out-of-sample evaluation; Scenario tree; Stochastic programming;
D O I：
10.1007/s10287-017-0279-4
中图分类号：
学科分类号：
摘要：
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. © 2017, Springer-Verlag Berlin Heidelberg.
引用
收藏
页码：333 / 365
页数：32
相关论文
共 42 条
  • [1] Bayraksan G., Morton D.P., Oskoorouchi M.R., Gray P., Greenberg H.J., Assessing solution quality in stochastic programs via sampling, Tutorials in operations research, (2009)
  • [2] Ben-Tal A., El Ghaoui L., Nemirovski A., Robust optimization, (2009)
  • [3] Birge J.R., Louveaux F., Introduction to stochastic programming, (1997)
  • [4] Chen M., Mehrotra S., Epi-convergent scenario generation method for stochastic problems via sparse grid, Stoch Program E-Print Ser, (2008)
  • [5] Chen M., Mehrotra S., Papp D., Scenario generation for stochastic optimization problems via the sparse grid method, Comput Optim Appl, 62, 3, pp. 669-692, (2015)
  • [6] Chiralaksanakul A., Morton D.P., Assessing policy quality in multi-stage stochastic programming, Stoch Program E-Print Ser (12), (2004)
  • [7] Defourny B., Ernst D., Wehenkel L., Sucar L.E., Morales E.F., Hoey J., Multistage stochastic programming: a scenario tree based approach, Decision theory models for applications in artificial intelligence: concepts and solutions. IGI Global, pp. 97-143, (2011)
  • [8] Defourny B., Ernst D., Wehenkel L., Scenario trees and policy selection for multistage stochastic programming using machine learning, INFORMS J Comput, 25, 3, pp. 488-501, (2013)
  • [9] Drew S.S., Homem-de Mello T., Quasi-Monte Carlo strategies for stochastic optimization. In: Proceedings of the 38th conference on Winter simulation. Winter Simulation Conference, pp 774–782, (2006)
  • [10] Dupacova J., Growe-Kuska N., Romisch W., Scenario reduction in stochastic programming, Math Program, 95, 3, pp. 493-511, (2003)
12345