IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v277y2019i3p918-929.html
   My bibliography  Save this article

Efficient solution selection for two-stage stochastic programs

Author

Listed:
  • Fei, Xin
  • Gülpınar, Nalân
  • Branke, Jürgen

Abstract

Sampling-based stochastic programs are extensively applied in practice. However, the resulting models tend to be computationally challenging. A reasonable number of samples needs to be identified to represent the random data, and a group of approximate models can then be constructed using such a number of samples. These approximate models can produce a set of potential solutions for the original model. In this paper, we consider the problem of allocating a finite computational budget among numerous potential solutions of a two-stage linear stochastic program, which aims to identify the best solution among potential ones by conducting simulation under a given computational budget. We propose a two-stage heuristic approach to solve the computational resource allocation problem. First, we utilise a Wasserstein-based screening rule to remove potentially inferior solutions from the simulation. Next, we use a ranking and selection technique to efficiently collect performance information of the remaining solutions. The performance of our approach is demonstrated through well-known benchmark problems. Results show that our method provides good trade-offs between computational effort and solution performance.

Suggested Citation

  • Fei, Xin & Gülpınar, Nalân & Branke, Jürgen, 2019. "Efficient solution selection for two-stage stochastic programs," European Journal of Operational Research, Elsevier, vol. 277(3), pages 918-929.
  • Handle: RePEc:eee:ejores:v:277:y:2019:i:3:p:918-929
    DOI: 10.1016/j.ejor.2019.02.015
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221719301432
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2019.02.015?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. Jie Xu & Si Zhang & Edward Huang & Chun-Hung Chen & Loo Hay Lee & Nurcin Celik, 2016. "MO2TOS: Multi-Fidelity Optimization with Ordinal Transformation and Optimal Sampling," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(03), pages 1-26, June.
    2. 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.
    3. Wolf, Christian & Fábián, Csaba I. & Koberstein, Achim & Suhl, Leena, 2014. "Applying oracles of on-demand accuracy in two-stage stochastic programming – A computational study," European Journal of Operational Research, Elsevier, vol. 239(2), pages 437-448.
    4. Raymond K. Cheung & Chuen-Yih Chen, 1998. "A Two-Stage Stochastic Network Model and Solution Methods for the Dynamic Empty Container Allocation Problem," Transportation Science, INFORMS, vol. 32(2), pages 142-162, May.
    5. Zhou, Zhe & Zhang, Jianyun & Liu, Pei & Li, Zheng & Georgiadis, Michael C. & Pistikopoulos, Efstratios N., 2013. "A two-stage stochastic programming model for the optimal design of distributed energy systems," Applied Energy, Elsevier, vol. 103(C), pages 135-144.
    6. George B. Dantzig & Philip Wolfe, 1960. "Decomposition Principle for Linear Programs," Operations Research, INFORMS, vol. 8(1), pages 101-111, February.
    7. Jeff Linderoth & Alexander Shapiro & Stephen Wright, 2006. "The empirical behavior of sampling methods for stochastic programming," Annals of Operations Research, Springer, vol. 142(1), pages 215-241, February.
    8. Barry L. Nelson & Julie Swann & David Goldsman & Wheyming Song, 2001. "Simple Procedures for Selecting the Best Simulated System When the Number of Alternatives is Large," Operations Research, INFORMS, vol. 49(6), pages 950-963, December.
    9. H. Heitsch & H. Leövey & W. Römisch, 2016. "Are Quasi-Monte Carlo algorithms efficient for two-stage stochastic programs?," Computational Optimization and Applications, Springer, vol. 65(3), pages 567-603, December.
    10. G. Guerkan & A.Y. Oezge & S.M. Robinson, 1994. "Sample-Path Optimization in Simulation," Working Papers wp94070, International Institute for Applied Systems Analysis.
    11. Panos Parpas & Berk Ustun & Mort Webster & Quang Kha Tran, 2015. "Importance Sampling in Stochastic Programming: A Markov Chain Monte Carlo Approach," INFORMS Journal on Computing, INFORMS, vol. 27(2), pages 358-377, May.
    12. Dillon, Mary & Oliveira, Fabricio & Abbasi, Babak, 2017. "A two-stage stochastic programming model for inventory management in the blood supply chain," International Journal of Production Economics, Elsevier, vol. 187(C), pages 27-41.
    13. Naomi Miller & Andrzej Ruszczyński, 2011. "Risk-Averse Two-Stage Stochastic Linear Programming: Modeling and Decomposition," Operations Research, INFORMS, vol. 59(1), pages 125-132, February.
    14. 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.
    15. Lee, Loo Hay & Chew, Ek Peng & Manikam, Puvaneswari, 2006. "A general framework on the simulation-based optimization under fixed computing budget," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1828-1841, November.
    16. Jonsson, Henrik & Jornsten, Kurt & Silver, Edward A., 1993. "Application of the scenario aggregation approach to a two-stage, stochastic, common component, inventory problem with a budget constraint," European Journal of Operational Research, Elsevier, vol. 68(2), pages 196-211, July.
    17. Jürgen Branke & Stephen E. Chick & Christian Schmidt, 2007. "Selecting a Selection Procedure," Management Science, INFORMS, vol. 53(12), pages 1916-1932, December.
    18. George B. Dantzig, 1955. "Linear Programming under Uncertainty," Management Science, INFORMS, vol. 1(3-4), pages 197-206, 04-07.
    19. G Barbarosoǧlu & Y Arda, 2004. "A two-stage stochastic programming framework for transportation planning in disaster response," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(1), pages 43-53, January.
    20. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    21. Santoso, Tjendera & Ahmed, Shabbir & Goetschalckx, Marc & Shapiro, Alexander, 2005. "A stochastic programming approach for supply chain network design under uncertainty," European Journal of Operational Research, Elsevier, vol. 167(1), pages 96-115, November.
    22. Birge, John R. & Louveaux, Francois V., 1988. "A multicut algorithm for two-stage stochastic linear programs," European Journal of Operational Research, Elsevier, vol. 34(3), pages 384-392, March.
    23. Holger Heitsch & Werner Römisch, 2009. "Scenario tree reduction for multistage stochastic programs," Computational Management Science, Springer, vol. 6(2), pages 117-133, May.
    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. Guo, Peijun, 2022. "Dynamic focus programming: A new approach to sequential decision problems under uncertainty," European Journal of Operational Research, Elsevier, vol. 303(1), pages 328-336.
    2. Wang, Tianxiang & Xu, Jie & Hu, Jian-Qiang & Chen, Chun-Hung, 2023. "Efficient estimation of a risk measure requiring two-stage simulation optimization," European Journal of Operational Research, Elsevier, vol. 305(3), pages 1355-1365.

    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. Emelogu, Adindu & Chowdhury, Sudipta & Marufuzzaman, Mohammad & Bian, Linkan & Eksioglu, Burak, 2016. "An enhanced sample average approximation method for stochastic optimization," International Journal of Production Economics, Elsevier, vol. 182(C), pages 230-252.
    2. Rebecca Stockbridge & Güzin Bayraksan, 2016. "Variance reduction in Monte Carlo sampling-based optimality gap estimators for two-stage stochastic linear programming," Computational Optimization and Applications, Springer, vol. 64(2), pages 407-431, June.
    3. Fan, Wei & Machemehl, Randy, 2004. "A Multi-stage Monte Carlo Sampling Based Stochastic Programming Model for the Dynamic Vehicle Allocation Problem," 45th Annual Transportation Research Forum, Evanston, Illinois, March 21-23, 2004 208244, Transportation Research Forum.
    4. Sanjeev Bhurtyal & Sarah Hernandez & Sandra Eksioglu & Manzi Yves, 2024. "A two-stage stochastic optimization model for port infrastructure planning," Maritime Economics & Logistics, Palgrave Macmillan;International Association of Maritime Economists (IAME), vol. 26(2), pages 185-211, June.
    5. Wang, Tianxiang & Xu, Jie & Hu, Jian-Qiang & Chen, Chun-Hung, 2023. "Efficient estimation of a risk measure requiring two-stage simulation optimization," European Journal of Operational Research, Elsevier, vol. 305(3), pages 1355-1365.
    6. Wim van Ackooij & Welington de Oliveira & Yongjia Song, 2018. "Adaptive Partition-Based Level Decomposition Methods for Solving Two-Stage Stochastic Programs with Fixed Recourse," INFORMS Journal on Computing, INFORMS, vol. 30(1), pages 57-70, February.
    7. Pavlo Glushko & Csaba I. Fábián & Achim Koberstein, 2022. "An L-shaped method with strengthened lift-and-project cuts," Computational Management Science, Springer, vol. 19(4), pages 539-565, October.
    8. Blanchot, Xavier & Clautiaux, François & Detienne, Boris & Froger, Aurélien & Ruiz, Manuel, 2023. "The Benders by batch algorithm: Design and stabilization of an enhanced algorithm to solve multicut Benders reformulation of two-stage stochastic programs," European Journal of Operational Research, Elsevier, vol. 309(1), pages 202-216.
    9. Fan, Wei, 2014. "Optimizing Strategic Allocation of Vehicles for One-Way Car-sharing Systems Under Demand Uncertainty," Journal of the Transportation Research Forum, Transportation Research Forum, vol. 53(3).
    10. Song, Haiqing & Cheung, Raymond K. & Wang, Haiyan, 2014. "An arc-exchange decomposition method for multistage dynamic networks with random arc capacities," European Journal of Operational Research, Elsevier, vol. 233(3), pages 474-487.
    11. 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.
    12. Fengqi You & Ignacio Grossmann, 2013. "Multicut Benders decomposition algorithm for process supply chain planning under uncertainty," Annals of Operations Research, Springer, vol. 210(1), pages 191-211, November.
    13. A. Ruszczynski, 1993. "Regularized Decomposition of Stochastic Programs: Algorithmic Techniques and Numerical Results," Working Papers wp93021, International Institute for Applied Systems Analysis.
    14. Ketabchi, Saeed & Behboodi-Kahoo, Malihe, 2015. "Augmented Lagrangian method within L-shaped method for stochastic linear programs," Applied Mathematics and Computation, Elsevier, vol. 266(C), pages 12-20.
    15. Xiaotie Chen & David L. Woodruff, 2024. "Distributions and bootstrap for data-based stochastic programming," Computational Management Science, Springer, vol. 21(1), pages 1-21, June.
    16. Maher, Stephen J., 2021. "Implementing the branch-and-cut approach for a general purpose Benders’ decomposition framework," European Journal of Operational Research, Elsevier, vol. 290(2), pages 479-498.
    17. Bhuiyan, Tanveer Hossain & Medal, Hugh R. & Harun, Sarah, 2020. "A stochastic programming model with endogenous and exogenous uncertainty for reliable network design under random disruption," European Journal of Operational Research, Elsevier, vol. 285(2), pages 670-694.
    18. Daniel Baena & Jordi Castro & Antonio Frangioni, 2020. "Stabilized Benders Methods for Large-Scale Combinatorial Optimization, with Application to Data Privacy," Management Science, INFORMS, vol. 66(7), pages 3051-3068, July.
    19. Gruson, Matthieu & Cordeau, Jean-François & Jans, Raf, 2021. "Benders decomposition for a stochastic three-level lot sizing and replenishment problem with a distribution structure," European Journal of Operational Research, Elsevier, vol. 291(1), pages 206-217.
    20. Ade Irawan, Chandra & Starita, Stefano & Chan, Hing Kai & Eskandarpour, Majid & Reihaneh, Mohammad, 2023. "Routing in offshore wind farms: A multi-period location and maintenance problem with joint use of a service operation vessel and a safe transfer boat," European Journal of Operational Research, Elsevier, vol. 307(1), pages 328-350.

    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:eee:ejores:v:277:y:2019:i:3:p:918-929. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.