IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v32y3i2020p805-821.html
   My bibliography  Save this article

Optimization-Driven Scenario Grouping

Author

Listed:
  • Kevin Ryan

    (H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

  • Shabbir Ahmed

    (H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

  • Santanu S. Dey

    (H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332)

  • Deepak Rajan

    (Lawrence Livermore National Laboratory, Livermore, California 94550)

  • Amelia Musselman

    (Lawrence Livermore National Laboratory, Livermore, California 94550)

  • Jean-Paul Watson

    (Sandia National Laboratory, Livermore, California 94550)

Abstract

Scenario decomposition algorithms for stochastic programs compute bounds by dualizing all nonanticipativity constraints and solving individual scenario problems independently. We develop an approach that improves on these bounds by reinforcing a carefully chosen subset of nonanticipativity constraints, effectively placing scenarios into groups . Specifically, we formulate an optimization problem for grouping scenarios that aims to improve the bound by optimizing a proxy metric based on information obtained from evaluating a subset of candidate feasible solutions. We show that the proposed grouping problem is NP-hard in general, identify a polynomially solvable case, and present two formulations for solving the problem: a matching formulation for a special case and a mixed-integer programming formulation for the general case. We use the proposed grouping scheme as a preprocessing step for a particular scenario decomposition algorithm and demonstrate its effectiveness in solving standard test instances of two-stage 0–1 stochastic programs. Using this approach, we are able to prove optimality for all previously unsolved instances of a standard test set. Additionally, we implement this scheme as a preprocessing step for PySP, a publicly available and widely used implementation of progressive hedging, and compare this grouping approach with standard grouping approaches on large-scale stochastic unit commitment instances. Finally, the idea is extended to propose a finitely convergent algorithm for two-stage stochastic programs with a finite feasible region.

Suggested Citation

  • Kevin Ryan & Shabbir Ahmed & Santanu S. Dey & Deepak Rajan & Amelia Musselman & Jean-Paul Watson, 2020. "Optimization-Driven Scenario Grouping," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 805-821, July.
    • Handle: RePEc:inm:orijoc:v:32:y:3:i:2020:p:805-821
    DOI: 10.1287/ijoc.2019.0924
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2019.0924
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2019.0924?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
    ---><---

    References listed on IDEAS

    as
    1. R. T. Rockafellar & Roger J.-B. Wets, 1991. "Scenarios and Policy Aggregation in Optimization Under Uncertainty," Mathematics of Operations Research, INFORMS, vol. 16(1), pages 119-147, February.
    2. Yan Deng & Shabbir Ahmed & Siqian Shen, 2018. "Parallel Scenario Decomposition of Risk-Averse 0-1 Stochastic Programs," INFORMS Journal on Computing, INFORMS, vol. 30(1), pages 90-105, February.
    3. Jean-Paul Watson & David Woodruff, 2011. "Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems," Computational Management Science, Springer, vol. 8(4), pages 355-370, November.
    4. Gustavo Angulo & Shabbir Ahmed & Santanu S. Dey, 2016. "Improving the Integer L-Shaped Method," INFORMS Journal on Computing, INFORMS, vol. 28(3), pages 483-499, August.
    5. Francesca Maggioni & Elisabetta Allevi & Marida Bertocchi, 2016. "Monotonic bounds in multistage mixed-integer stochastic programming," Computational Management Science, Springer, vol. 13(3), pages 423-457, July.
    6. Santanu S. Dey & Marco Molinaro & Qianyi Wang, 2018. "Analysis of Sparse Cutting Planes for Sparse MILPs with Applications to Stochastic MILPs," Mathematics of Operations Research, INFORMS, vol. 43(1), pages 304-332, February.
    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. Jiang, Xiaoping & Bai, Ruibin & Ren, Jianfeng & Li, Jiawei & Kendall, Graham, 2022. "Lagrange dual bound computation for stochastic service network design," European Journal of Operational Research, Elsevier, vol. 302(3), pages 1097-1112.
    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.

    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. Can Li & Ignacio E. Grossmann, 2019. "A finite $$\epsilon $$ϵ-convergence algorithm for two-stage stochastic convex nonlinear programs with mixed-binary first and second-stage variables," Journal of Global Optimization, Springer, vol. 75(4), pages 921-947, December.
    2. Ilke Bakir & Natashia Boland & Brian Dandurand & Alan Erera, 2020. "Sampling Scenario Set Partition Dual Bounds for Multistage Stochastic Programs," INFORMS Journal on Computing, INFORMS, vol. 32(1), pages 145-163, January.
    3. İ. Esra Büyüktahtakın, 2022. "Stage-t scenario dominance for risk-averse multi-stage stochastic mixed-integer programs," Annals of Operations Research, Springer, vol. 309(1), pages 1-35, February.
    4. Lee, Jinkyu & Bae, Sanghyeon & Kim, Woo Chang & Lee, Yongjae, 2023. "Value function gradient learning for large-scale multistage stochastic programming problems," European Journal of Operational Research, Elsevier, vol. 308(1), pages 321-335.
    5. Özgün Elçi & John Hooker, 2022. "Stochastic Planning and Scheduling with Logic-Based Benders Decomposition," INFORMS Journal on Computing, INFORMS, vol. 34(5), pages 2428-2442, September.
    6. Wu, Dexiang & Wu, Desheng Dash, 2020. "A decision support approach for two-stage multi-objective index tracking using improved lagrangian decomposition," Omega, Elsevier, vol. 91(C).
    7. Fan, Yingjie & Schwartz, Frank & Voß, Stefan, 2017. "Flexible supply chain planning based on variable transportation modes," International Journal of Production Economics, Elsevier, vol. 183(PC), pages 654-666.
    8. Gilles Bareilles & Yassine Laguel & Dmitry Grishchenko & Franck Iutzeler & Jérôme Malick, 2020. "Randomized Progressive Hedging methods for multi-stage stochastic programming," Annals of Operations Research, Springer, vol. 295(2), pages 535-560, December.
    9. Hu, Shaolong & Han, Chuanfeng & Dong, Zhijie Sasha & Meng, Lingpeng, 2019. "A multi-stage stochastic programming model for relief distribution considering the state of road network," Transportation Research Part B: Methodological, Elsevier, vol. 123(C), pages 64-87.
    10. Zhicheng Zhu & Yisha Xiang & Bo Zeng, 2021. "Multicomponent Maintenance Optimization: A Stochastic Programming Approach," INFORMS Journal on Computing, INFORMS, vol. 33(3), pages 898-914, July.
    11. Yongxi (Eric) Huang & Yueyue Fan & Chien-Wei Chen, 2014. "An Integrated Biofuel Supply Chain to Cope with Feedstock Seasonality and Uncertainty," Transportation Science, INFORMS, vol. 48(4), pages 540-554, November.
    12. J. Cole Smith, 2019. "In Memoriam: Shabbir Ahmed (1969–2019)," INFORMS Journal on Computing, INFORMS, vol. 31(4), pages 633-635, October.
    13. Kazemi Zanjani, Masoumeh & Sanei Bajgiran, Omid & Nourelfath, Mustapha, 2016. "A hybrid scenario cluster decomposition algorithm for supply chain tactical planning under uncertainty," European Journal of Operational Research, Elsevier, vol. 252(2), pages 466-476.
    14. Fan, Yueyue & Huang, Yongxi & Chen, Chien-Wei, 2012. "Multistage Infrastructure System Design: An Integrated Biofuel Supply Chain against Feedstock Seasonality and Uncertainty," Institute of Transportation Studies, Working Paper Series qt9g8413m5, Institute of Transportation Studies, UC Davis.
    15. Cristian Camilo Marín-Cano & Juan Esteban Sierra-Aguilar & Jesús M. López-Lezama & Álvaro Jaramillo-Duque & Juan G. Villegas, 2020. "A Novel Strategy to Reduce Computational Burden of the Stochastic Security Constrained Unit Commitment Problem," Energies, MDPI, vol. 13(15), pages 1-19, July.
    16. Bismark Singh & Bernard Knueven, 2021. "Lagrangian relaxation based heuristics for a chance-constrained optimization model of a hybrid solar-battery storage system," Journal of Global Optimization, Springer, vol. 80(4), pages 965-989, August.
    17. Giovanni Pantuso & Trine K. Boomsma, 2020. "On the number of stages in multistage stochastic programs," Annals of Operations Research, Springer, vol. 292(2), pages 581-603, September.
    18. Nur Banu Demir & Serhat Gul & Melih Çelik, 2021. "A stochastic programming approach for chemotherapy appointment scheduling," Naval Research Logistics (NRL), John Wiley & Sons, vol. 68(1), pages 112-133, February.
    19. Fadda, Edoardo & Perboli, Guido & Tadei, Roberto, 2019. "A progressive hedging method for the optimization of social engagement and opportunistic IoT problems," European Journal of Operational Research, Elsevier, vol. 277(2), pages 643-652.
    20. Aghalari, Amin & Nur, Farjana & Marufuzzaman, Mohammad, 2021. "Solving a stochastic inland waterway port management problem using a parallelized hybrid decomposition algorithm," Omega, Elsevier, vol. 102(C).

    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:inm:orijoc:v:32:y:3:i:2020:p:805-821. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.