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

Problem-based scenario generation by decomposing output distributions

Author

Listed:
  • Narum, Benjamin S.
  • Fairbrother, Jamie
  • Wallace, Stein W.

Abstract

Scenario generation is required for most applications of stochastic programming to evaluate the expected effect of decisions made under uncertainty. We propose a novel and effective problem-based scenario generation method for two-stage stochastic programming that is agnostic to the specific stochastic program and kind of distribution. Our contribution lies in studying how an output distribution may change across decisions and exploit this for scenario generation. From a collection of output distributions, we find a few components that largely compose these, and such components are used directly for scenario generation. Computationally, the procedure relies on evaluating the recourse function over a large discrete distribution across a set of candidate decisions, while the scenario set itself is found using standard and efficient linear algebra algorithms that scale well. The method’s effectiveness is demonstrated on four case study problems from typical applications of stochastic programming to show it is more effective than its distribution-based alternatives. Due to its generality, the method is especially well suited to address scenario generation for distributions that are particularly challenging.

Suggested Citation

  • Narum, Benjamin S. & Fairbrother, Jamie & Wallace, Stein W., 2024. "Problem-based scenario generation by decomposing output distributions," European Journal of Operational Research, Elsevier, vol. 318(1), pages 154-166.
    • Handle: RePEc:eee:ejores:v:318:y:2024:i:1:p:154-166
    DOI: 10.1016/j.ejor.2024.04.006
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221724002650
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2024.04.006?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. Yifei Zhao & Stein W. Wallace, 2016. "Appraising redundancy in facility layout," International Journal of Production Research, Taylor & Francis Journals, vol. 54(3), pages 665-679, February.
    2. Vaagen, Hajnalka & Wallace, Stein W. & Kaut, Michal, 2011. "Modelling consumer-directed substitution," International Journal of Production Economics, Elsevier, vol. 134(2), pages 388-397, December.
    3. Vit Prochazka & Stein W. Wallace, 2018. "Stochastic programs with binary distributions: structural properties of scenario trees and algorithms," Computational Management Science, Springer, vol. 15(3), pages 397-410, October.
    4. Vit Prochazka & Stein W. Wallace, 2020. "Scenario tree construction driven by heuristic solutions of the optimization problem," Computational Management Science, Springer, vol. 17(2), pages 277-307, June.
    5. 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.
    6. 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.
    7. Guglielmo Lulli & Suvrajeet Sen, 2004. "A Branch-and-Price Algorithm for Multistage Stochastic Integer Programming with Application to Stochastic Batch-Sizing Problems," Management Science, INFORMS, vol. 50(6), pages 786-796, June.
    8. 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.
    9. Vaagen, Hajnalka & Wallace, Stein W., 2008. "Product variety arising from hedging in the fashion supply chains," International Journal of Production Economics, Elsevier, vol. 114(2), pages 431-455, August.
    10. Ni, Jian & Chu, Lap Keung & Li, Qiang, 2017. "Capacity decisions with debt financing: The effects of agency problem," European Journal of Operational Research, Elsevier, vol. 261(3), pages 1158-1169.
    11. Aakil M. Caunhye & Xiaofeng Nie, 2018. "A Stochastic Programming Model for Casualty Response Planning During Catastrophic Health Events," Transportation Science, INFORMS, vol. 52(2), pages 437-453, March.
    12. Li, Baibing & Martin, Elaine B. & Morris, A. Julian, 2002. "On principal component analysis in L1," Computational Statistics & Data Analysis, Elsevier, vol. 40(3), pages 471-474, September.
    13. Zhaoxia Guo & Stein W. Wallace & Michal Kaut, 2019. "Vehicle Routing with Space- and Time-Correlated Stochastic Travel Times: Evaluating the Objective Function," INFORMS Journal on Computing, INFORMS, vol. 31(4), pages 654-670, October.
    14. Russell W. Bent & Pascal Van Hentenryck, 2004. "Scenario-Based Planning for Partially Dynamic Vehicle Routing with Stochastic Customers," Operations Research, INFORMS, vol. 52(6), pages 977-987, December.
    15. Rüdiger Schultz, 2000. "Some Aspects of Stability in Stochastic Programming," Annals of Operations Research, Springer, vol. 100(1), pages 55-84, December.
    16. Stein Wallace, 2010. "Stochastic programming and the option of doing it differently," Annals of Operations Research, Springer, vol. 177(1), pages 3-8, June.
    17. J. L. Midler & R. D. Wollmer, 1969. "Stochastic programming models for scheduling airlift operations," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 16(3), pages 315-330, September.
    Full references (including those not matched with items on IDEAS)

    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. 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.
    2. Wei Zhang & Kai Wang & Alexandre Jacquillat & Shuaian Wang, 2023. "Optimized Scenario Reduction: Solving Large-Scale Stochastic Programs with Quality Guarantees," INFORMS Journal on Computing, INFORMS, vol. 35(4), pages 886-908, July.
    3. Wen, Xin & Choi, Tsan-Ming & Chung, Sai-Ho, 2019. "Fashion retail supply chain management: A review of operational models," International Journal of Production Economics, Elsevier, vol. 207(C), pages 34-55.
    4. 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.
    5. Vit Prochazka & Stein W. Wallace, 2020. "Scenario tree construction driven by heuristic solutions of the optimization problem," Computational Management Science, Springer, vol. 17(2), pages 277-307, June.
    6. 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.
    7. Kaut, Michal & Vaagen, Hajnalka & Wallace, Stein W., 2021. "The combined impact of stochastic and correlated activity durations and design uncertainty on project plans," International Journal of Production Economics, Elsevier, vol. 233(C).
    8. Vaagen, Hajnalka & Kaut, Michal & Wallace, Stein W., 2017. "The impact of design uncertainty in engineer-to-order project planning," European Journal of Operational Research, Elsevier, vol. 261(3), pages 1098-1109.
    9. Aldasoro, Unai & Escudero, Laureano F. & Merino, María & Pérez, Gloria, 2017. "A parallel Branch-and-Fix Coordination based matheuristic algorithm for solving large sized multistage stochastic mixed 0–1 problems," European Journal of Operational Research, Elsevier, vol. 258(2), pages 590-606.
    10. Weskamp, Christoph & Koberstein, Achim & Schwartz, Frank & Suhl, Leena & Voß, Stefan, 2019. "A two-stage stochastic programming approach for identifying optimal postponement strategies in supply chains with uncertain demand," Omega, Elsevier, vol. 83(C), pages 123-138.
    11. Juan Carlos Chávez & Felipe J. Fonseca & Manuel Gómez-Zaldívar, 2017. "Resoluciones de disputas comerciales y desempeño económico regional en México. (Commercial Disputes Resolution and Regional Economic Performance in Mexico)," Ensayos Revista de Economia, Universidad Autonoma de Nuevo Leon, Facultad de Economia, vol. 0(1), pages 79-93, May.
    12. Chen, Ray-Bing & Chen, Ying & Härdle, Wolfgang K., 2014. "TVICA—Time varying independent component analysis and its application to financial data," Computational Statistics & Data Analysis, Elsevier, vol. 74(C), pages 95-109.
    13. Yan Yu Chen & Chun-Cheih Chao & Fu-Chen Liu & Po-Chen Hsu & Hsueh-Fen Chen & Shih-Chi Peng & Yung-Jen Chuang & Chung-Yu Lan & Wen-Ping Hsieh & David Shan Hill Wong, 2013. "Dynamic Transcript Profiling of Candida albicans Infection in Zebrafish: A Pathogen-Host Interaction Study," PLOS ONE, Public Library of Science, vol. 8(9), pages 1-16, September.
    14. Plat, Richard, 2009. "Stochastic portfolio specific mortality and the quantification of mortality basis risk," Insurance: Mathematics and Economics, Elsevier, vol. 45(1), pages 123-132, August.
    15. Kondylis, Athanassios & Whittaker, Joe, 2008. "Spectral preconditioning of Krylov spaces: Combining PLS and PC regression," Computational Statistics & Data Analysis, Elsevier, vol. 52(5), pages 2588-2603, January.
    16. Simplice A. Asongu & Nicholas M. Odhiambo, 2019. "Governance, capital flight and industrialisation in Africa," Journal of Economic Structures, Springer;Pan-Pacific Association of Input-Output Studies (PAPAIOS), vol. 8(1), pages 1-22, December.
    17. M. J. Aziakpono & S. Kleimeier & H. Sander, 2012. "Banking market integration in the SADC countries: evidence from interest rate analyses," Applied Economics, Taylor & Francis Journals, vol. 44(29), pages 3857-3876, October.
    18. Minjiao Zhang & Simge Küçükyavuz & Saumya Goel, 2014. "A Branch-and-Cut Method for Dynamic Decision Making Under Joint Chance Constraints," Management Science, INFORMS, vol. 60(5), pages 1317-1333, May.
    19. Bianca Maria Colosimo & Luca Pagani & Marco Grasso, 2024. "Modeling spatial point processes in video-imaging via Ripley’s K-function: an application to spatter analysis in additive manufacturing," Journal of Intelligent Manufacturing, Springer, vol. 35(1), pages 429-447, January.
    20. Michael Freimer & Jeffrey Linderoth & Douglas Thomas, 2012. "The impact of sampling methods on bias and variance in stochastic linear programs," Computational Optimization and Applications, Springer, vol. 51(1), pages 51-75, January.

    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:318:y:2024:i:1:p:154-166. 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.