Initialization and Local Search Methods Applied to the Set Covering Problem: A Systematic Mapping
Abstract
The set covering problem (SCP) is a classical combinatorial optimization problem part of Karp's 21 NP-complete problems. Many real-world applications can be modeled as set covering problems (SCPs), such as locating emergency services, military planning, and decision-making in a COVID-19 pandemic context. Among the approaches that this type of problem has solved are heuristic (H) and metaheuristic (MH) algorithms, which integrate iterative methods and procedures to explore and exploit the search space intelligently. In the present research, we carry out a systematic mapping of the literature focused on the initialization and local search methods used in these algorithms that have been applied to the SCP in order to identify them and that they can be applied in other algorithms. This mapping was carried out in three main stages: research planning, implementation, and documentation of results. The results indicate that the most used initialization method is random with heuristic search, and the inclusion of local search methods in MH algorithms improves the results obtained in comparison to those without local search. Moreover, initialization and local search methods can be used to modify other algorithms and evaluate the impact they generate on the results obtained.
Keywords
set covering problem, local search, systematic mapping, heuristics, initialization, metaheuristics, optimization
References
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, third edition. MIT Press, 2009. https://sd.blackball.lv/library/Introduction_to_Algorithms_Third_Edition_(2009).pdf
- Y. Deng, Y. Zhang, J. Pan, “Optimization for Locating Emergency Medical Service Facilities: A Case Study for Health Planning from China,” Risk Management and Healthcare Policy, vol. 14, pp. 1791–1802, 2021. https://doi.org/10.2147/RMHP.S304475 DOI: https://doi.org/10.2147/RMHP.S304475
- D. Sumrit, K. Thongsiriruengchai, “An Optimization Model for Advanced Life Support Ambulance Facility Location Problem,” Proceedings, vol. 39, no. 1, e10, 2020. https://doi.org/10.3390/proceedings2019039010 DOI: https://doi.org/10.3390/proceedings2019039010
- J. Purnomo, Z. Fanani, T. Domai, A. Hariswanto, “The model for determining location of naval base using ahp method and set covering problem,” Russian Journal of Agricultural and Socio-Economic Sciences, vol. 101, no. 5, pp. 122–131, 2020. https://doi.org/10.18551/rjoas.2020-05.13 DOI: https://doi.org/10.18551/rjoas.2020-05.13
- I. D. Argun, “An Overview on Set Covering Problems With a Focus on Military Applications,”in Operations Research for Military Organizations, pp. 54–66, 2019. https://doi.org/10.4018/978-1-5225-5513-1.CH003 DOI: https://doi.org/10.4018/978-1-5225-5513-1.ch003
- Q. Yong, D. Liu, G. Li, W. Wu, W. Sun, S. Liu, “Reducing exposure to COVID-19 by improving access to fever clinics: an empirical research of the Shenzhen area of China,” BMC Health Services Research, vol. 21, no. 1, pp. 1–10, 2021. https://doi.org/10.1186/S12913-021-06831-4 DOI: https://doi.org/10.1186/s12913-021-06831-4
- P. S. Muttaqin, R. A. Finata, A. A. Masturo, “Facility Location Model for Emergency Humanitarian Logistics Using Set Covering and Analytic Network Process (ANP) Method,” IPTEK Journal of Proceeding Series, no. 5, pp. 49–53, 2020. https://doi.org/10.12962/J23546026.Y2020I5.7931 DOI: https://doi.org/10.12962/j23546026.y2020i5.7931
- Y. Wang, D. Ouyang, L. Zhang, M. Yin, “A novel local search for unicost set covering problem using hyperedge configuration checking and weight diversity,” Science China Information Sciences, vol. 60, no. 6, e062103, 2017. https://doi.org/10.1007/s11432-015-5377-8 DOI: https://doi.org/10.1007/s11432-015-5377-8
- F. Xu, J. Li, “A hybrid encoded memetic algorithm for set covering problem,” in Proceedings - 2018 10th International Conference on Advanced Computational Intelligence, 2018, pp. 552–557. https://doi.org/10.1109/ICACI.2018.8377519 DOI: https://doi.org/10.1109/ICACI.2018.8377519
- M. Gendreau, J.-Y. Potvin, Handbook of Metaheuristics, 2010. DOI: https://doi.org/10.1007/978-1-4419-1665-5
- B. Kitchenham, S. Charters, Guidelines for performing Systematic Literature Reviews in Software Engineering, 2007.
- K. Petersen, R. Feldt, S. Mujtaba, M. Mattsson, “Systematic Mapping Studies in Software Engineering,” in 12th International Conference on Evaluation and Assessment in Software Engineering, 2008. https://doi.org/10.14236/EWIC/EASE2008.8 DOI: https://doi.org/10.14236/ewic/EASE2008.8
- T. Cañizares, C. Gómez, C. Pardo, O. S. Gómez, “What is there about scaling of agile software development? Preliminary findings from a systematic mapping study,” in XIV Jornadas Iberoamericanas de Ingenería de Software e Ingenería del Conocimiento, 2019, pp. 83–96.
- A. Bashab et al., “A systematic mapping study on solving university timetabling problems using meta-heuristic algorithms,” Neural Computing and Applications, vol. 32, no. 23, pp. 17397–17432, 2020. https://doi.org/10.1007/s00521-020-05110-3 DOI: https://doi.org/10.1007/s00521-020-05110-3
- J. García, G. Astorga, V. Yepes, “An analysis of a KNN perturbation operator: An application to the binarization of continuous metaheuristics,” Mathematics, vol. 9, no. 3, pp. 1–20, Jan. 2021. https://doi.org/10.3390/math9030225 DOI: https://doi.org/10.3390/math9030225
- J. García, B. Crawford, R. Soto, G. Astorga, “A clustering algorithm applied to the binarization of Swarm intelligence continuous metaheuristics,” Swarm and Evolutionary Computation, vol. 44, pp. 646–664, 2019. https://doi.org/10.1016/j.swevo.2018.08.006 DOI: https://doi.org/10.1016/j.swevo.2018.08.006
- B. Crawford et al., “A binary monkey search algorithm variation for solving the set covering problem,” Natural Computing, vol. 19, no. 4, pp. 825–841, 2020. https://doi.org/10.1007/s11047-019-09752-8 DOI: https://doi.org/10.1007/s11047-019-09752-8
- B. Crawford et al., “Binary Fruit Fly Swarm Algorithms for the Set Covering Problem,” Computers, Materials & Continua, vol. 71, no. 2, pp. 4295–4318, 2022. http://doi.org/10.32604/cmc.2022.023068 DOI: https://doi.org/10.32604/cmc.2022.023068
- V. Reyes, I. Araya, “A GRASP-based scheme for the set covering problem,” Operational Research, vol. 21, no. 4, pp. 2391–2408, 2019. https://doi.org/10.1007/s12351-019-00514-z DOI: https://doi.org/10.1007/s12351-019-00514-z
- H. Razip, M. N. Zakaria, “Combining approximation algorithm with genetic algorithm at the initial population for NP-complete problem,” in IEEE Student Conference on Research and Development: Inspiring Technology for Humanity, 2018, pp. 98–103. https://doi.org/10.1109/SCORED.2017.8305413 DOI: https://doi.org/10.1109/SCORED.2017.8305413
- H. Razip, N. Zakaria, “Genetic Algorithm with Approximation Algorithm Based Initial Population for the Set Covering Problem,” Springer, Singapore, 2021, pp. 59–78. https://doi.org/10.1007/978-981-16-3246-4_6 DOI: https://doi.org/10.1007/978-981-16-3246-4_6
- Z. Lei, S. Cai, “Solving set cover and dominating set via maximum satisfiability,” in AAAI, vol. 34, no. 02, pp. 1569–1576, 2020. https://doi.org/10.1609/aaai.v34i02.5517 DOI: https://doi.org/10.1609/aaai.v34i02.5517
- M. Pinard, L. Moalic, M. Brévilliers, J. Lepagnot, L. Idoumghar, “A memetic approach for the unicost set covering problem,” Lecture Notes in Computer Science, vol. 12096, pp. 233–248, 2020. https://doi.org/10.1007/978-3-030-53552-0_23 DOI: https://doi.org/10.1007/978-3-030-53552-0_23
- M. Brévilliers, J. Lepagnot, L. Idoumghar, M. Rebai, J. Kritter, “Hybrid differential evolution algorithms for the optimal camera placement problem,” Journal of Systems and Information Technology, vol. 20, no. 4, pp. 446–467, 2018. https://doi.org/10.1108/JSIT-09-2017-0081 DOI: https://doi.org/10.1108/JSIT-09-2017-0081
- M. F. L. Schmitt, M. H. Mulati, A. A. Constantino, F. Hernandes, T. A. Hild, “Ant-set: A subset-oriented ant colony optimization algorithm for the set covering problem,” Journal of Universal Computer Science, vol. 26, no. 2, pp. 293–316, 2020. https://doi.org/10.3897/jucs.2020.016 DOI: https://doi.org/10.3897/jucs.2020.016
- J. Bailey, D. Budgen, M. Turner, B. Kitchenham, P. Brereton, S. Linkman, “Evidence relating to object-oriented software design: A survey,” in First International Symposium on Empirical Software Engineering and Measurement, 2007, pp. 482–484. https://doi.org/10.1109/ESEM.2007.58 DOI: https://doi.org/10.1109/ESEM.2007.58
- L. Jorquera, P. Valenzuela, M. Valenzuela, H. Pinto, “A Binary Ant Lion Optimisation Algorithm Applied to the Set Covering Problem,” in Computer Science On-line Conference, 2019, pp. 156–167. https://doi.org/10.1007/978-3-030-19810-7_16 DOI: https://doi.org/10.1007/978-3-030-19810-7_16
- L. Pavez, F. Altimiras, G. Villavicencio, “A Percentil Gravitational Search Algorithm an Aplication to the Set Covering Problem,” in Proceedings of the Computational Methods in Systems and Software, 2020, pp. 663–673. https://doi.org/10.1007/978-3-030-63319-6_62 DOI: https://doi.org/10.1007/978-3-030-63319-6_62
- A. Fernández, A. Peña, M. Valenzuela, H. Pinto, “A Binary Percentile Sin-Cosine Optimisation Algorithm Applied to the Set Covering Problem,” in Proceedings of the Computational Methods in Systems and Software, 2019, pp. 285–295. https://doi.org/10.1007/978-3-030-00211-4_25 DOI: https://doi.org/10.1007/978-3-030-00211-4_25
- L. Jorquera, P. Valenzuela, F. Altimiras, P. Moraga, G. Villavicencio, “A Percentil Bat Algorithm an Application to the Set Covering Problem,” in Computer Science On-line Conference, 2020, pp. 223–233. https://doi.org/10.1007/978-3-030-51971-1_18 DOI: https://doi.org/10.1007/978-3-030-51971-1_18
- L. Jorquera, P. Valenzuela, L. Causa, P. Moraga, G. Villavicencio, “A Percentile Firefly Algorithm an Application to the Set Covering Problem,” in Lecture Notes in Networks and Systems, vol. 229, pp. 750–759, 2021. https://doi.org/10.1007/978-3-030-77445-5_67 DOI: https://doi.org/10.1007/978-3-030-77445-5_67
- G. Villavicencio, M. Valenzuela, L. Causa, P. Moraga, H. Pinto, “A Machine Learning Firefly Algorithm Applied to the Matrix Covering Problem,” in Computer Science On-line Conference, 2021, pp. 316–325. https://doi.org/10.1007/978-3-030-77445-5_29 DOI: https://doi.org/10.1007/978-3-030-77445-5_29
- L. Pavez, F. Altimiras, G. Villavicencio, “A K-means Bat Optimisation Algorithm Applied to the Set Covering Problem,” in Proceedings of the Computational Methods in Systems and Software, 2020, pp. 622–632. https://doi.org/10.1007/978-3-030-63319-6_58 DOI: https://doi.org/10.1007/978-3-030-63319-6_58
- G. Villavicencio, M. Valenzuela, F. Altimiras, P. Moraga, H. Pinto, “A K-Means Grasshopper Optimisation Algorithm Applied to the Set Covering Problem,” in Computer Science On-line Conference, 2020, pp. 312–323. https://doi.org/10.1007/978-3-030-51971-1_25 DOI: https://doi.org/10.1007/978-3-030-51971-1_25
- M. Valenzuela, P. Moraga, L. Causa, H. Pinto, J.-M. Rubio, “A Machine Learning Whale Algorithm Applied to the Matrix Covering Problem,” in Proceedings of the Computational Methods in Systems and Software, 2021, pp. 413–422. https://doi.org/10.1007/978-3-030-90321-3_33 DOI: https://doi.org/10.1007/978-3-030-90321-3_33
Downloads
Download data is not yet available.