IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v75y2019i2d10.1007_s10898-019-00816-8.html
   My bibliography  Save this article

A generalized Benders decomposition-based branch and cut algorithm for two-stage stochastic programs with nonconvex constraints and mixed-binary first and second stage variables

Author

Listed:
  • Can Li

    (Carnegie Mellon University)

  • Ignacio E. Grossmann

    (Carnegie Mellon University)

Abstract

In this paper, we propose a generalized Benders decomposition-based branch and cut algorithm for solving two stage stochastic mixed-integer nonlinear programs (SMINLPs) with mixed binary first and second stage variables. At a high level, the proposed decomposition algorithm performs spatial branch and bound search on the first stage variables. Each node in the branch and bound search is solved with a Benders-like decomposition algorithm where both Lagrangean cuts and Benders cuts are included in the Benders master problem. The Lagrangean cuts are derived from Lagrangean decomposition. The Benders cuts are derived from the Benders subproblems, which are convexified by cutting planes, such as rank-one lift-and-project cuts. We prove that the proposed algorithm converges in the limit. We apply the proposed algorithm to a stochastic pooling problem, a crude selection problem, and a storage design problem. The performance of the proposed algorithm is compared with a Lagrangean decomposition-based branch and bound algorithm and solving the corresponding deterministic equivalent with the solvers including BARON, ANTIGONE, and SCIP.

Suggested Citation

  • Can Li & Ignacio E. Grossmann, 2019. "A generalized Benders decomposition-based branch and cut algorithm for two-stage stochastic programs with nonconvex constraints and mixed-binary first and second stage variables," Journal of Global Optimization, Springer, vol. 75(2), pages 247-272, October.
    • Handle: RePEc:spr:jglopt:v:75:y:2019:i:2:d:10.1007_s10898-019-00816-8
    DOI: 10.1007/s10898-019-00816-8
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-019-00816-8
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10898-019-00816-8?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. Shabbir Ahmed & Renan Garcia, 2003. "Dynamic Capacity Acquisition and Assignment under Uncertainty," Annals of Operations Research, Springer, vol. 124(1), pages 267-283, November.
    2. Xiang Li & Asgeir Tomasgard & Paul Barton, 2012. "Decomposition strategy for the stochastic pooling problem," Journal of Global Optimization, Springer, vol. 54(4), pages 765-790, December.
    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. Alonso-Ayuso, Antonio & Escudero, Laureano F. & Teresa Ortuno, M., 2003. "BFC, A branch-and-fix coordination algorithmic framework for solving some types of stochastic pure and mixed 0-1 programs," European Journal of Operational Research, Elsevier, vol. 151(3), pages 503-519, December.
    5. Xiang Li & Asgeir Tomasgard & Paul I. Barton, 2011. "Nonconvex Generalized Benders Decomposition for Stochastic Separable Mixed-Integer Nonlinear Programs," Journal of Optimization Theory and Applications, Springer, vol. 151(3), pages 425-454, December.
    6. Semih Atakan & Suvrajeet Sen, 2018. "A Progressive Hedging based branch-and-bound algorithm for mixed-integer stochastic programs," Computational Management Science, Springer, vol. 15(3), pages 501-540, October.
    7. E. Mijangos, 2015. "An algorithm for two-stage stochastic mixed-integer nonlinear convex problems," Annals of Operations Research, Springer, vol. 235(1), pages 581-598, December.
    8. Emmanuel Ogbe & Xiang Li, 2019. "A joint decomposition method for global optimization of multiscenario nonconvex mixed-integer nonlinear programs," Journal of Global Optimization, Springer, vol. 75(3), pages 595-629, November.
    9. 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.
    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. MacNeil, Moira & Bodur, Merve, 2024. "Leveraging decision diagrams to solve two-stage stochastic programs with binary recourse and logical linking constraints," European Journal of Operational Research, Elsevier, vol. 315(1), pages 228-241.
    2. Jia-Jiang Lin & Feng Xu & Xiong-Lin Luo, 2023. "Nonconvex sensitivity-based generalized Benders decomposition," Journal of Global Optimization, Springer, vol. 86(1), pages 37-60, May.
    3. Yin, Yue & Liu, Tianqi & Wu, Lei & He, Chuan & Liu, Yikui, 2021. "Frequency-constrained multi-source power system scheduling against N-1 contingency and renewable uncertainty," Energy, Elsevier, vol. 216(C).
    4. Andrew Allman & Qi Zhang, 2021. "Branch-and-price for a class of nonconvex mixed-integer nonlinear programs," Journal of Global Optimization, Springer, vol. 81(4), pages 861-880, December.
    5. Kuttner, Leopold, 2022. "Integrated scheduling and bidding of power and reserve of energy resource aggregators with storage plants," Applied Energy, Elsevier, vol. 321(C).

    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. Frank, Stephen M. & Rebennack, Steffen, 2015. "Optimal design of mixed AC–DC distribution systems for commercial buildings: A Nonconvex Generalized Benders Decomposition approach," European Journal of Operational Research, Elsevier, vol. 242(3), pages 710-729.
    3. Jia-Jiang Lin & Feng Xu & Xiong-Lin Luo, 2023. "Nonconvex sensitivity-based generalized Benders decomposition," Journal of Global Optimization, Springer, vol. 86(1), pages 37-60, May.
    4. MacNeil, Moira & Bodur, Merve, 2024. "Leveraging decision diagrams to solve two-stage stochastic programs with binary recourse and logical linking constraints," European Journal of Operational Research, Elsevier, vol. 315(1), pages 228-241.
    5. Andrew C. Trapp & Oleg A. Prokopyev & Andrew J. Schaefer, 2013. "On a Level-Set Characterization of the Value Function of an Integer Program and Its Application to Stochastic Programming," Operations Research, INFORMS, vol. 61(2), pages 498-511, April.
    6. Ogbe, Emmanuel & Li, Xiang, 2017. "A new cross decomposition method for stochastic mixed-integer linear programming," European Journal of Operational Research, Elsevier, vol. 256(2), pages 487-499.
    7. Miguel A. Lejeune & François Margot, 2016. "Solving Chance-Constrained Optimization Problems with Stochastic Quadratic Inequalities," Operations Research, INFORMS, vol. 64(4), pages 939-957, August.
    8. Lamas, Patricio & Goycoolea, Marcos & Pagnoncelli, Bernardo & Newman, Alexandra, 2024. "A target-time-windows technique for project scheduling under uncertainty," European Journal of Operational Research, Elsevier, vol. 314(2), pages 792-806.
    9. Manish Bansal & Yingqiu Zhang, 2021. "Scenario-based cuts for structured two-stage stochastic and distributionally robust p-order conic mixed integer programs," Journal of Global Optimization, Springer, vol. 81(2), pages 391-433, October.
    10. 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.
    11. Fan-Yun Meng & Li-Ping Pang & Jian Lv & Jin-He Wang, 2017. "An approximate bundle method for solving nonsmooth equilibrium problems," Journal of Global Optimization, Springer, vol. 68(3), pages 537-562, July.
    12. Martínez-Costa, Carme & Mas-Machuca, Marta & Benedito, Ernest & Corominas, Albert, 2014. "A review of mathematical programming models for strategic capacity planning in manufacturing," International Journal of Production Economics, Elsevier, vol. 153(C), pages 66-85.
    13. Beltran-Royo, C., 2017. "Two-stage stochastic mixed-integer linear programming: The conditional scenario approach," Omega, Elsevier, vol. 70(C), pages 31-42.
    14. Šárka Štádlerová & Sanjay Dominik Jena & Peter Schütz, 2023. "Using Lagrangian relaxation to locate hydrogen production facilities under uncertain demand: a case study from Norway," Computational Management Science, Springer, vol. 20(1), pages 1-32, December.
    15. J. Cole Smith, 2019. "In Memoriam: Shabbir Ahmed (1969–2019)," INFORMS Journal on Computing, INFORMS, vol. 31(4), pages 633-635, October.
    16. Atakan, Semih & Gangammanavar, Harsha & Sen, Suvrajeet, 2022. "Towards a sustainable power grid: Stochastic hierarchical planning for high renewable integration," European Journal of Operational Research, Elsevier, vol. 302(1), pages 381-391.
    17. Agustı´n, A. & Alonso-Ayuso, A. & Escudero, L.F. & Pizarro, C., 2012. "On air traffic flow management with rerouting. Part I: Deterministic case," European Journal of Operational Research, Elsevier, vol. 219(1), pages 156-166.
    18. Alonso-Ayuso, Antonio & Escudero, Laureano F. & Guignard, Monique & Weintraub, Andres, 2018. "Risk management for forestry planning under uncertainty in demand and prices," European Journal of Operational Research, Elsevier, vol. 267(3), pages 1051-1074.
    19. Nesbitt, Peter & Blake, Lewis R. & Lamas, Patricio & Goycoolea, Marcos & Pagnoncelli, Bernardo K. & Newman, Alexandra & Brickey, Andrea, 2021. "Underground mine scheduling under uncertainty," European Journal of Operational Research, Elsevier, vol. 294(1), pages 340-352.

    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:jglopt:v:75:y:2019:i:2:d:10.1007_s10898-019-00816-8. 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.