IDEAS home Printed from https://ideas.repec.org/a/gam/jeners/v14y2021i20p6503-d653369.html
   My bibliography  Save this article

Generalized Benders Decomposition Method to Solve Big Mixed-Integer Nonlinear Optimization Problems with Convex Objective and Constraints Functions

Author

Listed:
  • Andrzej Karbowski

    (Research and Academic Computer Network NASK—National Research Institute, ul. Kolska 12, 01-045 Warsaw, Poland)

Abstract

The paper presents the Generalized Benders Decomposition (GBD) method, which is now one of the basic approaches to solve big mixed-integer nonlinear optimization problems. It concentrates on the basic formulation with convex objectives and constraints functions. Apart from the classical projection and representation theorems, a unified formulation of the master problem with nonlinear and linear cuts will be given. For the latter case the most effective and, at the same time, easy to implement computational algorithms will be pointed out.

Suggested Citation

  • Andrzej Karbowski, 2021. "Generalized Benders Decomposition Method to Solve Big Mixed-Integer Nonlinear Optimization Problems with Convex Objective and Constraints Functions," Energies, MDPI, vol. 14(20), pages 1-18, October.
    • Handle: RePEc:gam:jeners:v:14:y:2021:i:20:p:6503-:d:653369
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/1996-1073/14/20/6503/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/1996-1073/14/20/6503/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    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. Marufuzzaman, Mohammad & Ekşioğlu, Sandra Duni, 2017. "Managing congestion in supply chains via dynamic freight routing: An application in the biomass supply chain," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 99(C), pages 54-76.
    3. A. M. Geoffrion & G. W. Graves, 1974. "Multicommodity Distribution System Design by Benders Decomposition," Management Science, INFORMS, vol. 20(5), pages 822-844, January.
    4. Lu, Jie & Gupte, Akshay & Huang, Yongxi, 2018. "A mean-risk mixed integer nonlinear program for transportation network protection," European Journal of Operational Research, Elsevier, vol. 265(1), pages 277-289.
    5. Joe Naoum‐Sawaya & Samir Elhedhli, 2010. "A nested benders decomposition approach for telecommunication network planning," Naval Research Logistics (NRL), John Wiley & Sons, vol. 57(6), pages 519-539, September.
    6. Duan Li & Xiaoling Sun, 2006. "Nonlinear Integer Programming," International Series in Operations Research and Management Science, Springer, number 978-0-387-32995-6, September.
    7. Osman, Hany & Demirli, Kudret, 2010. "A bilinear goal programming model and a modified Benders decomposition algorithm for supply chain reconfiguration and supplier selection," International Journal of Production Economics, Elsevier, vol. 124(1), pages 97-105, March.
    8. Ximing Cai & Daene C. McKinney & Leon S. Lasdon & David W. Watkins, 2001. "Solving Large Nonconvex Water Resources Management Models Using Generalized Benders Decomposition," Operations Research, INFORMS, vol. 49(2), pages 235-245, April.
    9. Shuang Chen & Joseph Geunes, 2013. "Optimal allocation of stock levels and stochastic customer demands to a capacitated resource," Annals of Operations Research, Springer, vol. 203(1), pages 33-54, March.
    10. 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.
    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. Ihnat Ruksha & Andrzej Karbowski, 2022. "Decomposition Methods for the Network Optimization Problem of Simultaneous Routing and Bandwidth Allocation Based on Lagrangian Relaxation," Energies, MDPI, vol. 15(20), pages 1-28, October.

    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. Mariel, Katharina & Minner, Stefan, 2017. "Benders decomposition for a strategic network design problem under NAFTA local content requirements," Omega, Elsevier, vol. 68(C), pages 62-75.
    2. 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.
    3. Enrique Castillo & Roberto Mínguez & Antonio Conejo & Beatriz Pérez & Oscar Fontenla, 2013. "Estimating the parameters of a fatigue model using Benders’ decomposition," Annals of Operations Research, Springer, vol. 210(1), pages 309-331, November.
    4. Sinha, Ankur & Das, Arka & Anand, Guneshwar & Jayaswal, Sachin, 2021. "A General Purpose Exact Solution Method for Mixed Integer Concave Minimization Problems," IIMA Working Papers WP 2021-03-01, Indian Institute of Management Ahmedabad, Research and Publication Department.
    5. Bei, Xiaoqiang & Zhu, Xiaoyan & Coit, David W., 2019. "A risk-averse stochastic program for integrated system design and preventive maintenance planning," European Journal of Operational Research, Elsevier, vol. 276(2), pages 536-548.
    6. Ricardo Saraiva de Camargo & Gilberto de Miranda & Henrique Pacca L. Luna, 2009. "Benders Decomposition for Hub Location Problems with Economies of Scale," Transportation Science, INFORMS, vol. 43(1), pages 86-97, February.
    7. Roberto Mínguez & Antonio Conejo & Enrique Castillo, 2013. "Optimal engineering design via Benders’ decomposition," Annals of Operations Research, Springer, vol. 210(1), pages 273-293, November.
    8. Sinha, Ankur & Das, Arka & Anand, Guneshwar & Jayaswal, Sachin, 2021. "A General Purpose Exact Solution Method for Mixed Integer Concave Minimization Problems (revised as on 12/08/2021)," IIMA Working Papers WP 2021-03-01, Indian Institute of Management Ahmedabad, Research and Publication Department.
    9. 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.
    10. Elisangela Martins de Sá & Ivan Contreras & Jean-François Cordeau & Ricardo Saraiva de Camargo & Gilberto de Miranda, 2015. "The Hub Line Location Problem," Transportation Science, INFORMS, vol. 49(3), pages 500-518, August.
    11. Brech, Claus-Henning & Ernst, Andreas & Kolisch, Rainer, 2019. "Scheduling medical residents’ training at university hospitals," European Journal of Operational Research, Elsevier, vol. 274(1), pages 253-266.
    12. Halit Üster & Panitan Kewcharoenwong, 2011. "Strategic Design and Analysis of a Relay Network in Truckload Transportation," Transportation Science, INFORMS, vol. 45(4), pages 505-523, November.
    13. García Cáceres, Rafael Guillermo & Aráoz Durand, Julián Arturo & Gómez, Fernando Palacios, 2009. "Integral analysis method - IAM," European Journal of Operational Research, Elsevier, vol. 192(3), pages 891-903, February.
    14. Osman, Hany & Demirli, Kudret, 2010. "A bilinear goal programming model and a modified Benders decomposition algorithm for supply chain reconfiguration and supplier selection," International Journal of Production Economics, Elsevier, vol. 124(1), pages 97-105, March.
    15. Li, Xin & Pan, Yanchun & Jiang, Shiqiang & Huang, Qiang & Chen, Zhimin & Zhang, Mingxia & Zhang, Zuoyao, 2021. "Locate vaccination stations considering travel distance, operational cost, and work schedule," Omega, Elsevier, vol. 101(C).
    16. Mazzola, Joseph B. & Neebe, Alan W., 1999. "Lagrangian-relaxation-based solution procedures for a multiproduct capacitated facility location problem with choice of facility type," European Journal of Operational Research, Elsevier, vol. 115(2), pages 285-299, June.
    17. Lahlum, Suzanne M. & Dooley, Frank J., 1996. "The Optimal Number and Size of Fertilizer Plants Under Hazardous Materials Regulations," MPC Reports 231704, North Dakota State University, Upper Great Plains Transportation Institute.
    18. 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.
    19. Cascón, J.M. & González-Arteaga, T. & de Andrés Calle, R., 2019. "Reaching social consensus family budgets: The Spanish case," Omega, Elsevier, vol. 86(C), pages 28-41.
    20. Joseph B. Mazzola & Robert H. Schantz, 1997. "Multiple‐facility loading under capacity‐based economies of scope," Naval Research Logistics (NRL), John Wiley & Sons, vol. 44(3), pages 229-256, April.

    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:gam:jeners:v:14:y:2021:i:20:p:6503-:d:653369. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.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.