A Generalized Benders Decomposition for Mixed-Integer Nonlinear Programming: Theory and Applications

Fadiah Hasna Nadiatul Haq, Diah Chaerani, Anita Triska

Abstract


This paper comprehensively explains how to solve mixed-integer nonlinear programming (MINLP) models using the generalized benders decomposition (GBD) method. The MINLP problem is an optimization model in which some variables must be integers and the objective function or constraints are nonlinear.  The GBD method is an extension of the Benders Decomposition (BD) method, effectively handles the characteristics of the MINLP  model, where the model has nonlinear properties and involves two types of variables, namely continuous variables and integer variables. The GBD method decomposes the problem into primal and master problems that are solved alternately until the optimal solution is found. The main difference between the GBD and BD methods is that GBD uses nonlinear duality in the main problem so that GBD can solve the nonlinear problem, whereas BD applies linear duality. This paper also presents some theorem proofs related to GBD that were not presented in detail in the previous literature. The application of the GBD method is also presented to demonstrate how the method can be effectively used to solve real-world MINLP problems.


Keywords


Optimization; Mixed-Integer Nonlinear Programming; Generalized Benders Decomposition

Full Text:

PDF

References


[1] S. S. Rao, Engineering Optimization: Theory and Practice, Fourth Edition. New Jersey: John Wiley & Sons, 2009.

[2] R. W. Sayekti, “Model Optimasi Alternatif Pola Tanam, Untuk Mendapatkan Luas Tanam dan Keuntungan yang Optimum (Studi Kasus di Dam Jatimlerek, Kabupaten Jombang),” J. Water Resour. Eng., vol. 1, no. 2, pp. 115–126, 2010, [Online]. Available: https://jurnalpengairan.ub.ac.id/index.php/jtp/article/view/107/105

[3] A. Z. Irmansyah, D. Chaerani, and E. Rusyaman, “A Systematic Review on Integer Multi-objective Adjustable Robust Counterpart Optimization Model Using Benders Decomposition,” JTAM (Jurnal Teor. dan Apl. Mat., vol. 6, no. 3, pp. 678–698, Nov. 2022, doi: 10.31764/jtam.v6i3.8578.

[4] M. S. Bazaraa, H. D. Sherali, and C. M. Shetty, Nonlinear Programming: Theory and Algorithms. Wiley, 2006. [Online]. Available: https://books.google.co.id/books?id=Mw5HFRkCdQgC

[5] C. Li and I. E. Grossmann, “An improved L-shaped method for two-stage convex 0–1 mixed integer nonlinear stochastic programs,” Comput. Chem. Eng., vol. 112, pp. 165–179, 2018, doi: https://doi.org/10.1016/j.compchemeng.2018.01.017.

[6] J. F. Benders, “Partitioning procedures for solving mixed-variables programming problems,” Numer. Math., vol. 4, no. 1, pp. 238–252, 1962, doi: 10.1007/BF01386316.

[7] A. M. Geoffrion, “Generalized Benders decomposition,” J. Optim. Theory Appl., vol. 10, no. 4, pp. 237–260, 1972, doi: 10.1007/BF00934810.

[8] C. Floudas, “Generalized benders decomposition Generalized Benders Decomposition,” 2008, pp. 1162–1175. doi: 10.1007/978-0-387-74759-0_201.

[9] A. Karbowski, “Generalized benders decomposition method to solve big mixed-integer nonlinear optimization problems with convex objective and constraints functions,” Energies, vol. 14, no. 20, 2021, doi: 10.3390/en14206503.

[10] K. H. Chung, B. H. Kim, and D. Hur, “Distributed implementation of generation scheduling algorithm on interconnected power systems,” Energy Convers. Manag., vol. 52, no. 12, pp. 3457–3464, 2011, doi: https://doi.org/10.1016/j.enconman.2010.10.006.

[11] J. Lu, A. Gupte, and Y. Huang, “A mean-risk mixed integer nonlinear program for transportation network protection,” Eur. J. Oper. Res., vol. 265, no. 1, pp. 277–289, 2018, doi: https://doi.org/10.1016/j.ejor.2017.07.025.

[12] H. Osman and K. Demirli, “A bilinear goal programming model and a modified Benders decomposition algorithm for supply chain reconfiguration and supplier selection,” Int. J. Prod. Econ., vol. 124, no. 1, pp. 97–105, 2010, doi: https://doi.org/10.1016/j.ijpe.2009.10.012.

[13] N. V. Sahinidis, “Mixed-integer nonlinear programming 2018,” Optim. Eng., vol. 20, no. 2, pp. 301–306, 2019, doi: 10.1007/s11081-019-09438-1.

[14] J. S. Arora, Introduction to Optimum Design, 5th ed. Elsevier Science, 2024. [Online]. Available: https://books.google.co.id/books?id=jPL3zwEACAAJ

[15] A. Karbowski, “Generalized Benders Decomposition Method to Solve Big Mixed-Integer Nonlinear Optimization Problems with Convex Objective and Constraints Functions,” energies, vol. 14, no. 20, 2021.




DOI: https://doi.org/10.18860/ca.v9i2.29398

Refbacks

  • There are currently no refbacks.


Copyright (c) 2024 Fadiah Hasna Nadiatul Haq, Diah Chaerani, Anita Triska

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Editorial Office
Mathematics Department,
Universitas Islam Negeri Maulana Malik Ibrahim Malang
Gajayana Street 50 Malang, East Java, Indonesia 65144
Faximile (+62) 341 558933
e-mail: cauchy@uin-malang.ac.id

Creative Commons License
CAUCHY: Jurnal Matematika Murni dan Aplikasi is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.