Systematic Literature Review for Robust Mixed-Integer Linear Programming Models Using Benders Decomposition in Facility Location Problems

Fadiah Hasna Nadiatul Haq, Diah Chaerani, Anita Triska

Abstract


The robust Mixed-Integer Linear Programming (MILP) model is an approach to address uncertainty in linear optimization involving integer and continuous variables, which can be solved using the Benders Decomposition method. One of its applications is facility location problems, which often face demand, costs, and capacity uncertainties. This article presents a systematic literature review (SLR) on solving robust MILP models using the Benders Decomposition method and its application to facility location problems. The objectives are to explore the state-of-the-art and research trends, identify issues modeled as robust MILP and solved using Benders Decomposition, and determine the most frequently used uncertainty sets. SLR was conducted using the Preferred Reporting Items for Systematic Review and Meta-Analysis (PRISMA) method on the Scopus, Science Direct, and Dimensions databases for the last five years of publication, with bibliometric analysis using VOSviewer and RStudio. The results show that there are limited articles that discuss the solution of the robust MILP model on the problem of facility location with the ellipsoidal uncertainty set. In addition, the Benders Decomposition method is widely used to solve robust MILP problems in energy, logistics, supply chains, and scheduling, with interval uncertainty sets being the most common. This topic is an influential theme and has the potential to be explored further.


Keywords


Systematic Literature Review; Robust Optimization; Mixed-Integer Linear Programming; Benders Decomposition; Facility Location Problem

Full Text:

PDF

References


[1] S. S. Rao, Engineering Optimization: Theory and Practice, Fourth Edition. New Jersey: John Wiley & Sons, 2009. [Online]. Available: https://industri.fatek.unpatti.ac.id/wp-content/uploads/2019/03/018-Engineering-Optimization-Theory-and-Practice-Singiresu-S.-Rao-Edisi-4-2009.pdf

[2] D. Chaerani, S. Saksmilena, A. Z. Irmansyah, E. Hertini, E. Rusyaman, and E. Paulus, “Benders Decomposition Method on Adjustable Robust Counterpart Optimization Model for Internet Shopping Online Problem,” Computation, vol. 11, no. 2, Feb. 2023, doi: 10.3390/computation11020037.

[3] D. Chaerani, A. Z. Irmansyah, T. Perdana, and N. Gusriani, “Contribution of Robust Optimization on Handling Agricultural Processed Products Supply Chain Problem During Covid-19 Pandemic,” Uncertain Supply Chain Manag., vol. 10, no. 1, pp. 239–254, 2022, doi: 10.5267/j.uscm.2021.9.004.

[4] B. L. Gorissen, I. Yanikoğlu, and D. den Hertog, “A practical guide to robust optimization,” Omega (United Kingdom), vol. 53, pp. 124–137, Jun. 2015, doi: 10.1016/j.omega.2014.12.006.

[5] Y. Ji et al., “A mixed integer robust programming model for two-echelon inventory routing problem of perishable products,” Phys. A Stat. Mech. its Appl., vol. 548, p. 124481, 2020, doi: https://doi.org/10.1016/j.physa.2020.124481.

[6] K. G. Pradana, D. Saepudin, and I. Kurniawan, “Optimasi Portofolio Saham dengan Pendekatan Ellipsoidal Uncertainty Set Studi Kasus : IDX30,” e-Proceeding Eng., vol. 8, no. 1, pp. 780–802, 2021.

[7] O. Baron, J. Milner, and H. Naseraldin, “Facility Location : A Robust Optimization Approach,” vol. 20, no. 5, pp. 772–785, 2011.

[8] R. Z. Farahani, S. Fallah, R. Ruiz, S. Hosseini, and N. Asgari, “OR models in urban service facility location: A critical review of applications and future developments,” Eur. J. Oper. Res., vol. 276, no. 1, pp. 1–27, 2019, doi: 10.1016/j.ejor.2018.07.036.

[9] C. Cheng, Q. Yu, Y. Adulyasak, and L. M. Rousseau, “Distributionally robust facility location with uncertain facility capacity and customer demand,” Omega (United Kingdom), vol. 122, no. August 2022, p. 102959, 2024, doi: 10.1016/j.omega.2023.102959.

[10] D. C. Fransisca, Sukono, D. Chaerani, and Nurfadhlina, “Robust Portfolio Mean-Variance Optimization for Capital Allocation in Stock Investment Using the Genetic Algorithm : A Systematic Literature Review,” Computatin, vol. 12, no. 166, 2024, doi: https://doi.org/10.3390/computation12080166.

[11] D. Chaerani, A. Shuib, T. Perdana, and A. Z. Irmansyah, “Systematic Literature Review on Robust Optimization in Solving Sustainable Development Goals (SDGs) Problems during the COVID-19 Pandemic,” Sustain., vol. 15, no. 7, 2023, doi: 10.3390/su15075654.

[12] L. V Snyder and L. V Snyder, “Facility location under uncertainty : a review Facility location under uncertainty : a review,” vol. 8830, no. 2006, 2007, doi: 10.1080/07408170500216480.

[13] F. Clautiaux and I. Ljubić, “Last fifty years of integer linear programming : A focus on recent practical advances,” Eur. J. Oper. Res., no. July, 2024, doi: 10.1016/j.ejor.2024.11.018.

[14] V. Marianov and H. A. Eiselt, “Fifty Years of Location Theory - A Selective Review,” Eur. J. Oper. Res., vol. 318, no. 3, pp. 701–718, 2024, doi: 10.1016/j.ejor.2024.01.036.

[15] I. Dissanayake and M. Gunathilake, “A comprehensive survey of recent advances in facility location problems : Models , solution methods , and applications,” J. Sustain. Dev. Transp. Logist., vol. 9, no. 2, pp. 78–91, 2024, doi: 10.14254/jsdtl.2024.9-2.6.

[16] F. S. Hillier and G. J. Lieberman, Introduction to Operations Research, 9th ed. Newyork: McGraw-Hill, 2010. [Online]. Available: http://www.maths.lse.ac.uk/Personal/stengel/HillierLieberman9thEdition.pdf

[17] H. Golmohamadi, “Demand-side management in industrial sector: A review of heavy industries,” Renew. Sustain. Energy Rev., vol. 156, no. June 2021, p. 111963, 2022, doi: 10.1016/j.rser.2021.111963.

[18] H. Saito and K. Murota, “Benders Decomposition Approach to Robust Mixed Integer Programming,” Pacific J. Optim., vol. 3, no. 1, pp. 99–112, 2007.

[19] J. M. Mulvey, R. Vanderbei, S. A. Zenios, J. M. Mulvey, and R. J. Vanderbei, “Robust Optimization of Large-Scale Systems,” vol. 43, no. 2, pp. 264–281, 1995, doi: 10.1287/opre.43.2.264.

[20] A. Ben-Tal and A. Nemirovski, “Robust optimization – methodology and applications,” Math. Program., vol. 92, no. 3, pp. 453–480, 2002, doi: 10.1007/s101070100286.

[21] P. Thagard, “Computational Tractability and Conceptual Coherence,” Can. J. Philos., vol. 23, no. 3, 1993.

[22] 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.

[23] R. Rahmaniani, T. G. Crainic, M. Gendreau, and W. Rei, “The Benders decomposition algorithm: A literature review,” Eur. J. Oper. Res., vol. 259, no. 3, pp. 801–817, 2017, doi: 10.1016/j.ejor.2016.12.005.

[24] J. Bisschop, Optimization Modeling AIMMS. Netherlands: AIMMS B. V., 2006. [Online]. Available: www.aimms.com

[25] E. Stovold, D. Beecher, R. Foxlee, and A. Noel-storr, “Study flow diagrams in Cochrane systematic review updates : an adapted PRISMA flow diagram,” pp. 1–5, 2014.

[26] N. Panic, E. Leoncini, G. De Belvis, W. Ricciardi, and S. Boccia, “Evaluation of the Endorsement of the Preferred Reporting Items for Systematic Reviews and Meta- Analysis ( PRISMA ) Statement on the Quality of Published Systematic Review and Meta-Analyses,” vol. 8, no. 12, 2013, doi: 10.1371/journal.pone.0083138.

[27] F. Firdaniza, B. N. Ruchjana, and D. Chaerani, “Information Diffusion Model in Twitter : A Systematic Literature Review,” 2022.

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

[29] I. Suryana, D. Chaerani, A. S. Abdullah, A. S. Prabuwono, K. R. A. Muslihin, and A. Z. Irmansyah, “Systematic Literature Review for Optimization System with Advection-Diffusion-Reaction Non-Linear Equation in Water Quality,” IAENG Int. J. Appl. Math., vol. 54, no. 12, pp. 2541–2554, 2024.

[30] D. Chaerani, I. Royana, and E. Hertini, “Model Optimisasi Robust untuk Mengatasi Ketidaktentuan Estimasi Durasi Operasi pada Masalah Penjadwalan Ruang Operasi Rumah Sakit,” J. Tek. Ind., vol. 19, no. 1, pp. 55–66, 2017, doi: 10.9744/jti.19.1.55-66.

[31] J. Jeong and S. Park, “A robust contingency-constrained unit commitment with an N-αk security criterion,” Int. J. Electr. Power Energy Syst., vol. 123, p. 106148, 2020, doi: https://doi.org/10.1016/j.ijepes.2020.106148.

[32] X. Liu and C. Kwon, “Exact robust solutions for the combined facility location and network design problem in hazardous materials transportation,” IISE Trans., vol. 52, no. 10, pp. 1156–1172, 2020, doi: 10.1080/24725854.2019.1697017.

[33] S. Chandra, P. N. Yasasvi, A. Mohapatra, and S. C. Srivastava, “Optimal transmission switching with injection uncertainties,” IEEE Power Energy Soc. Gen. Meet., vol. 2020-Augus, pp. 1–5, 2020, doi: 10.1109/PESGM41954.2020.9281842.

[34] N. Balouka and I. Cohen, “A robust optimization approach for the multi-mode resource-constrained project scheduling problem,” Eur. J. Oper. Res., vol. 291, no. 2, pp. 457–470, 2021, doi: 10.1016/j.ejor.2019.09.052.

[35] E. Conde and M. Leal, “A robust optimization model for distribution network design under a mixed integer set of scenarios,” Comput. Oper. Res., vol. 136, no. August 2019, p. 105493, 2021, doi: 10.1016/j.cor.2021.105493.

[36] W. Lefever, F. A. Touzout, K. Hadj-Hamou, and E.-H. Aghezzaf, “Benders’ decomposition for robust travel time-constrained inventory routing problem,” Int. J. Prod. Res., vol. 59, no. 2, pp. 342 – 366, 2021, doi: 10.1080/00207543.2019.1695167.

[37] W. Li et al., “Robust transmission expansion planning model considering multiple uncertainties and active load,” Glob. Energy Interconnect., vol. 4, no. 5, pp. 476–484, 2021, doi: https://doi.org/10.1016/j.gloei.2021.11.009.

[38] N. Ghaffarinasab, “Exact algorithms for the robust uncapacitated multiple allocation p-hub median problem,” Optim. Lett., vol. 16, no. 6, pp. 1745 – 1772, 2022, doi: 10.1007/s11590-021-01799-w.

[39] H. Cipta, S. Suwilo, Sutarman, and H. Mawengkang, “Improved Benders decomposition approach to complete robust optimization in box-interval,” Bull. Electr. Eng. Informatics, vol. 11, no. 5, pp. 2949–2957, 2022, doi: 10.11591/eei.v11i5.4394.

[40] C. Liu, Y. Ji, and X. Li, “Closed-Loop Supply Chain Network Design with Flexible Capacity under Uncertain Environment,” Sustainability, vol. 15, no. 19, p. 14565, 2023, doi: 10.3390/su151914565.

[41] M. Sadeghloo, S. Emami, and A. Divsalar, “A Benders decomposition algorithm for the multi-mode resource-constrained multi-project scheduling problem with uncertainty,” Ann. Oper. Res., vol. 339, no. 3, pp. 1637 – 1677, 2024, doi: 10.1007/s10479-023-05403-5.

[42] S. Jiu, D. Wang, and Z. Ma, “Benders decomposition for robust distribution network design and operations in online retailing,” Eur. J. Oper. Res., vol. 315, no. 3, pp. 1069–1082, 2024, doi: 10.1016/j.ejor.2024.01.046.

[43] D. Chauhan, A. Unnikrishnan, S. D. Boyles, and P. N. Patil, “Robust maximum flow network interdiction considering uncertainties in arc capacity and resource consumption,” Ann. Oper. Res., vol. 335, no. 2, pp. 689–725, 2024, doi: 10.1007/s10479-023-05812-6.

[44] M. Deng, T. Li, J. Ding, Y. Zhou, and L. Zhang, “Stochastic and robust truck-and-drone routing problems with deadlines: A Benders decomposition approach,” Transp. Res. Part E Logist. Transp. Rev., vol. 190, p. 103709, 2024, doi: 10.1016/j.tre.2024.103709.




DOI: https://doi.org/10.18860/cauchy.v10i1.31539

Refbacks

  • There are currently no refbacks.


Copyright (c) 2025 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.