IDEAS home Printed from https://ideas.repec.org/a/spr/annopr/v210y2013i1p191-21110.1007-s10479-011-0974-4.html
   My bibliography  Save this article

Multicut Benders decomposition algorithm for process supply chain planning under uncertainty

Author

Listed:
  • Fengqi You
  • Ignacio Grossmann

Abstract

In this paper, we present a multicut version of the Benders decomposition method for solving two-stage stochastic linear programming problems, including stochastic mixed-integer programs with only continuous recourse (two-stage) variables. The main idea is to add one cut per realization of uncertainty to the master problem in each iteration, that is, as many Benders cuts as the number of scenarios added to the master problem in each iteration. Two examples are presented to illustrate the application of the proposed algorithm. One involves production-transportation planning under demand uncertainty, and the other one involves multiperiod planning of global, multiproduct chemical supply chains under demand and freight rate uncertainty. Computational studies show that while both the standard and the multicut versions of the Benders decomposition method can solve large-scale stochastic programming problems with reasonable computational effort, significant savings in CPU time can be achieved by using the proposed multicut algorithm. Copyright Springer Science+Business Media, LLC 2013

Suggested Citation

  • 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.
    • Handle: RePEc:spr:annopr:v:210:y:2013:i:1:p:191-211:10.1007/s10479-011-0974-4
    DOI: 10.1007/s10479-011-0974-4
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10479-011-0974-4
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10479-011-0974-4?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. Trukhanov, Svyatoslav & Ntaimo, Lewis & Schaefer, Andrew, 2010. "Adaptive multicut aggregation for two-stage stochastic linear programs with recourse," European Journal of Operational Research, Elsevier, vol. 206(2), pages 395-406, October.
    2. T W Archibald & C S Buchanan & K I M McKinnon & L C Thomas, 1999. "Nested Benders decomposition and dynamic programming for reservoir optimisation," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 50(5), pages 468-479, May.
    3. Lewis Ntaimo, 2010. "Disjunctive Decomposition for Two-Stage Stochastic Mixed-Binary Programs with Random Recourse," Operations Research, INFORMS, vol. 58(1), pages 229-243, February.
    4. 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.
    5. 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.
    6. L. Escudero & A. Garín & M. Merino & G. Pérez, 2007. "A two-stage stochastic integer programming approach as a mixture of Branch-and-Fix Coordination and Benders Decomposition schemes," Annals of Operations Research, Springer, vol. 152(1), pages 395-420, July.
    7. Jesús Latorre & Santiago Cerisola & Andrés Ramos & Rafael Palacios, 2009. "Analysis of stochastic problem decomposition algorithms in computational grids," Annals of Operations Research, Springer, vol. 166(1), pages 355-373, February.
    8. Julia L. Higle & Suvrajeet Sen, 1991. "Stochastic Decomposition: An Algorithm for Two-Stage Linear Programs with Recourse," Mathematics of Operations Research, INFORMS, vol. 16(3), pages 650-669, August.
    9. Emmanuel Fragnière & Jacek Gondzio & Jean-Philippe Vial, 2000. "Building and Solving Large-Scale Stochastic Programs on an Affordable Distributed Computing System," Annals of Operations Research, Springer, vol. 99(1), pages 167-187, December.
    10. 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.
    11. John M. Mulvey & Andrzej Ruszczyński, 1995. "A New Scenario Decomposition Method for Large-Scale Stochastic Optimization," Operations Research, INFORMS, vol. 43(3), pages 477-490, June.
    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. Fragkogios, Antonios & Qiu, Yuzhuo & Saharidis, Georgios K.D. & Pardalos, Panos M., 2024. "An accelerated benders decomposition algorithm for the solution of the multi-trip time-dependent vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 317(2), pages 500-514.
    2. Denise D. Tönissen & Joachim J. Arts & Zuo-Jun Max Shen, 2021. "A column-and-constraint generation algorithm for two-stage stochastic programming problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(3), pages 781-798, October.
    3. J. F. F. Almeida & S. V. Conceição & L. R. Pinto & B. R. P. Oliveira & L. F. Rodrigues, 2022. "Optimal sales and operations planning for integrated steel industries," Annals of Operations Research, Springer, vol. 315(2), pages 773-790, August.
    4. Zahra Azadi & Harsha Gangammanavar & Sandra Eksioglu, 2020. "Developing childhood vaccine administration and inventory replenishment policies that minimize open vial wastage," Annals of Operations Research, Springer, vol. 292(1), pages 215-247, September.
    5. Arslan, Okan & Karaşan, Oya Ekin, 2016. "A Benders decomposition approach for the charging station location problem with plug-in hybrid electric vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 670-695.
    6. Hermann, Alexander & Jensen, Tue Vissing & Østergaard, Jacob & Kazempour, Jalal, 2022. "A complementarity model for electric power transmission-distribution coordination under uncertainty," European Journal of Operational Research, Elsevier, vol. 299(1), pages 313-329.
    7. Li, Xiaohong & Yang, Dong & Hu, Mengqi, 2018. "A scenario-based stochastic programming approach for the product configuration problem under uncertainties and carbon emission regulations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 115(C), pages 126-146.
    8. Amorim, Pedro & Curcio, Eduardo & Almada-Lobo, Bernardo & Barbosa-Póvoa, Ana P.F.D. & Grossmann, Ignacio E., 2016. "Supplier selection in the processed food industry under uncertainty," European Journal of Operational Research, Elsevier, vol. 252(3), pages 801-814.
    9. 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.
    10. Babak Saleck Pay & Yongjia Song, 2020. "Partition-based decomposition algorithms for two-stage Stochastic integer programs with continuous recourse," Annals of Operations Research, Springer, vol. 284(2), pages 583-604, January.
    11. Nicoletti, Jack & Ning, Chao & You, Fengqi, 2019. "Incorporating agricultural waste-to-energy pathways into biomass product and process network through data-driven nonlinear adaptive robust optimization," Energy, Elsevier, vol. 180(C), pages 556-571.

    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. 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.
    2. Babak Saleck Pay & Yongjia Song, 2020. "Partition-based decomposition algorithms for two-stage Stochastic integer programs with continuous recourse," Annals of Operations Research, Springer, vol. 284(2), pages 583-604, January.
    3. Jacek Gondzio & Roy Kouwenberg, 2001. "High-Performance Computing for Asset-Liability Management," Operations Research, INFORMS, vol. 49(6), pages 879-891, December.
    4. Trukhanov, Svyatoslav & Ntaimo, Lewis & Schaefer, Andrew, 2010. "Adaptive multicut aggregation for two-stage stochastic linear programs with recourse," European Journal of Operational Research, Elsevier, vol. 206(2), pages 395-406, October.
    5. Martin Biel & Mikael Johansson, 2022. "Efficient Stochastic Programming in Julia," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 1885-1902, July.
    6. Suvrajeet Sen & Yifan Liu, 2016. "Mitigating Uncertainty via Compromise Decisions in Two-Stage Stochastic Linear Programming: Variance Reduction," Operations Research, INFORMS, vol. 64(6), pages 1422-1437, December.
    7. Wolf, Christian & Koberstein, Achim, 2013. "Dynamic sequencing and cut consolidation for the parallel hybrid-cut nested L-shaped method," European Journal of Operational Research, Elsevier, vol. 230(1), pages 143-156.
    8. 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.
    9. 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.
    10. Li, Na & Jiang, Yue & Zhang, Zhi-Hai, 2021. "A two-stage ambiguous stochastic program for electric vehicle charging station location problem with valet charging service," Transportation Research Part B: Methodological, Elsevier, vol. 153(C), pages 149-171.
    11. Li, Xiaohong & Yang, Dong & Hu, Mengqi, 2018. "A scenario-based stochastic programming approach for the product configuration problem under uncertainties and carbon emission regulations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 115(C), pages 126-146.
    12. 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.
    13. Riis, Morten & Andersen, Kim Allan, 2005. "Applying the minimax criterion in stochastic recourse programs," European Journal of Operational Research, Elsevier, vol. 165(3), pages 569-584, September.
    14. 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.
    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. 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.
    18. 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.
    19. Aydin, Nezir & Murat, Alper, 2013. "A swarm intelligence based sample average approximation algorithm for the capacitated reliable facility location problem," International Journal of Production Economics, Elsevier, vol. 145(1), pages 173-183.
    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.

    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:spr:annopr:v:210:y:2013:i:1:p:191-211:10.1007/s10479-011-0974-4. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.