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

Strengthened Benders Cuts for Stochastic Integer Programs with Continuous Recourse

Author

Listed:
  • Merve Bodur

    (Department of Mechanical and Industrial Engineering, University of Toronto, Toronto, Ontario M5S 3G8, Canada)

  • Sanjeeb Dash

    (Mathematical Sciences Department, IBM T.J. Watson Research Center, Yorktown Heights, New York 10598)

  • Oktay Günlük

    (Mathematical Sciences Department, IBM T.J. Watson Research Center, Yorktown Heights, New York 10598)

  • James Luedtke

    (Department of Industrial and Systems Engineering, University of Wisconsin-Madison, Madison, Wisconsin 53706)

Abstract

With stochastic integer programming as the motivating application, we investigate techniques to use integrality constraints to obtain improved cuts within a Benders decomposition algorithm. We compare the effect of using cuts in two ways: (i) cut-and-project, where integrality constraints are used to derive cuts in the extended variable space, and Benders cuts are then used to project the resulting improved relaxation, and (ii) project-and-cut, where integrality constraints are used to derive cuts directly in the Benders reformulation. For the case of split cuts, we demonstrate that although these approaches yield equivalent relaxations when considering a single split disjunction, cut-and-project yields stronger relaxations in general when using multiple split disjunctions. Computational results illustrate that the difference can be very large, and demonstrate that using split cuts within the cut-and-project framework can significantly improve the performance of Benders decomposition.

Suggested Citation

  • Merve Bodur & Sanjeeb Dash & Oktay Günlük & James Luedtke, 2017. "Strengthened Benders Cuts for Stochastic Integer Programs with Continuous Recourse," INFORMS Journal on Computing, INFORMS, vol. 29(1), pages 77-91, February.
  • Handle: RePEc:inm:orijoc:v:29:y:2017:i:1:p:77-91
    DOI: 10.1287/ijoc.2016.0717
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2016.0717
    Download Restriction: no

    File URL: https://libkey.io/10.1287/ijoc.2016.0717?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. Lewis Ntaimo, 2013. "Fenchel decomposition for stochastic mixed-integer programming," Journal of Global Optimization, Springer, vol. 55(1), pages 141-163, January.
    2. Daniel Bienstock & Oktay Günlük, 1996. "Capacitated Network Design---Polyhedral Structure and Computation," INFORMS Journal on Computing, INFORMS, vol. 8(3), pages 243-259, August.
    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. Liu, Kanglin & Yang, Liu & Zhao, Yejia & Zhang, Zhi-Hai, 2023. "Multi-period stochastic programming for relief delivery considering evolving transportation network and temporary facility relocation/closure," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 180(C).
    2. Onur Tavaslıoğlu & Oleg A. Prokopyev & Andrew J. Schaefer, 2019. "Solving Stochastic and Bilevel Mixed-Integer Programs via a Generalized Value Function," Operations Research, INFORMS, vol. 67(6), pages 1659-1677, November.
    3. Stephen J. Maher, 2021. "Enhancing large neighbourhood search heuristics for Benders’ decomposition," Journal of Heuristics, Springer, vol. 27(4), pages 615-648, August.
    4. Zheng, Xiaojin & Yin, Meixia & Zhang, Yanxia, 2019. "Integrated optimization of location, inventory and routing in supply chain network design," Transportation Research Part B: Methodological, Elsevier, vol. 121(C), pages 1-20.
    5. Beck, Yasmine & Ljubić, Ivana & Schmidt, Martin, 2023. "A survey on bilevel optimization under uncertainty," European Journal of Operational Research, Elsevier, vol. 311(2), pages 401-426.
    6. Rui Chen & James Luedtke, 2022. "On Generating Lagrangian Cuts for Two-Stage Stochastic Integer Programs," INFORMS Journal on Computing, INFORMS, vol. 34(4), pages 2332-2349, July.
    7. 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.
    8. 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.
    9. Bahman Naderi & Vahid Roshanaei & Mehmet A. Begen & Dionne M. Aleman & David R. Urbach, 2021. "Increased Surgical Capacity without Additional Resources: Generalized Operating Room Planning and Scheduling," Production and Operations Management, Production and Operations Management Society, vol. 30(8), pages 2608-2635, August.
    10. Ward Romeijnders & Niels van der Laan, 2020. "Pseudo-Valid Cutting Planes for Two-Stage Mixed-Integer Stochastic Programs with Right-Hand-Side Uncertainty," Operations Research, INFORMS, vol. 68(4), pages 1199-1217, July.
    11. Xiao Liu & Simge Küçükyavuz, 2018. "A polyhedral study of the static probabilistic lot-sizing problem," Annals of Operations Research, Springer, vol. 261(1), pages 233-254, February.
    12. Ragheb Rahmaniani & Shabbir Ahmed & Teodor Gabriel Crainic & Michel Gendreau & Walter Rei, 2020. "The Benders Dual Decomposition Method," Operations Research, INFORMS, vol. 68(3), pages 878-895, May.
    13. 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.
    14. Ksciuk, Jana & Kuhlemann, Stefan & Tierney, Kevin & Koberstein, Achim, 2023. "Uncertainty in maritime ship routing and scheduling: A Literature review," European Journal of Operational Research, Elsevier, vol. 308(2), pages 499-524.
    15. 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.
    16. Soovin Yoon & Laura A. Albert & Veronica M. White, 2021. "A Stochastic Programming Approach for Locating and Dispatching Two Types of Ambulances," Transportation Science, INFORMS, vol. 55(2), pages 275-296, March.

    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. Agarwal, Y.K. & Aneja, Y.P. & Jayaswal, Sachin, 2022. "Directed fixed charge multicommodity network design: A cutting plane approach using polar duality," European Journal of Operational Research, Elsevier, vol. 299(1), pages 118-136.
    2. Merve Bodur & James R. Luedtke, 2017. "Mixed-Integer Rounding Enhanced Benders Decomposition for Multiclass Service-System Staffing and Scheduling with Arrival Rate Uncertainty," Management Science, INFORMS, vol. 63(7), pages 2073-2091, July.
    3. Kathryn M. Schumacher & Amy E. M. Cohn & Richard Li-Yang Chen, 2017. "Algorithm for the N -2 Security-Constrained Unit Commitment Problem with Transmission Switching," INFORMS Journal on Computing, INFORMS, vol. 29(4), pages 645-659, November.
    4. M Riis & A J V Skriver & S F Møller, 2005. "Internet protocol network design with uncertain demand," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(10), pages 1184-1195, October.
    5. Fragkos, Ioannis & Cordeau, Jean-François & Jans, Raf, 2021. "Decomposition methods for large-scale network expansion problems," Transportation Research Part B: Methodological, Elsevier, vol. 144(C), pages 60-80.
    6. Sridhar, Varadharajan & Park, June S., 2000. "Benders-and-cut algorithm for fixed-charge capacitated network design problem," European Journal of Operational Research, Elsevier, vol. 125(3), pages 622-632, September.
    7. Cheng Guo & Merve Bodur & Dionne M. Aleman & David R. Urbach, 2021. "Logic-Based Benders Decomposition and Binary Decision Diagram Based Approaches for Stochastic Distributed Operating Room Scheduling," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1551-1569, October.
    8. Andrew P. Armacost & Cynthia Barnhart & Keith A. Ware, 2002. "Composite Variable Formulations for Express Shipment Service Network Design," Transportation Science, INFORMS, vol. 36(1), pages 1-20, February.
    9. Keely L. Croxton & Bernard Gendron & Thomas L. Magnanti, 2007. "Variable Disaggregation in Network Flow Problems with Piecewise Linear Costs," Operations Research, INFORMS, vol. 55(1), pages 146-157, February.
    10. Majid Taghavi & Kai Huang, 2016. "A multi‐stage stochastic programming approach for network capacity expansion with multiple sources of capacity," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(8), pages 600-614, December.
    11. Mervat Chouman & Teodor Gabriel Crainic & Bernard Gendron, 2018. "The impact of filtering in a branch-and-cut algorithm for multicommodity capacitated fixed charge network design," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 6(2), pages 143-184, June.
    12. Jack Brimberg & Pierre Hansen & Keh-Wei Lin & Nenad Mladenović & MichÈle Breton, 2003. "An Oil Pipeline Design Problem," Operations Research, INFORMS, vol. 51(2), pages 228-239, April.
    13. Anantaram Balakrishnan & Thomas L. Magnanti & Joel S. Sokol & Yi Wang, 2002. "Spare-Capacity Assignment For Line Restoration Using a Single-Facility Type," Operations Research, INFORMS, vol. 50(4), pages 617-635, August.
    14. Ayşegül Altın & Hande Yaman & Mustafa Ç. Pınar, 2011. "The Robust Network Loading Problem Under Hose Demand Uncertainty: Formulation, Polyhedral Analysis, and Computations," INFORMS Journal on Computing, INFORMS, vol. 23(1), pages 75-89, February.
    15. Hugues Marchand & Laurence A. Wolsey, 2001. "Aggregation and Mixed Integer Rounding to Solve MIPs," Operations Research, INFORMS, vol. 49(3), pages 363-371, June.
    16. van der Laan, Niels & Romeijnders, Ward & van der Vlerk, M.H., 2017. "Higher-order total variation bounds for expectations of periodic functions and simple integer recourse approximations," Research Report 2017-014-EEF, University of Groningen, Research Institute SOM (Systems, Organisations and Management).
    17. Christina N. Burt & Lou Caccetta, 2014. "Equipment Selection for Surface Mining: A Review," Interfaces, INFORMS, vol. 44(2), pages 143-162, April.
    18. Onur Tavaslıoğlu & Oleg A. Prokopyev & Andrew J. Schaefer, 2019. "Solving Stochastic and Bilevel Mixed-Integer Programs via a Generalized Value Function," Operations Research, INFORMS, vol. 67(6), pages 1659-1677, November.
    19. Jose L. Andrade-Pineda & David Canca & Pedro L. Gonzalez-R, 2017. "On modelling non-linear quantity discounts in a supplier selection problem by mixed linear integer optimization," Annals of Operations Research, Springer, vol. 258(2), pages 301-346, November.
    20. 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.

    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:29:y:2017:i:1:p:77-91. 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.