Skip to main navigation menu Skip to main content Skip to site footer

Vol. 32 No. 63 (2023)
January-March 2023 (Continuous Publication)

Papers

Initialization and Local Search Methods Applied to the Set Covering Problem: A Systematic Mapping

https://doi.org/10.19053/01211129.v32.n63.2023.15235

Published 2023-02-28

Nelson-Enrique Quemá-Taimbud
Universidad del Cauca

Martha-Eliana Mendoza-Becerra
Universidad del Cauca

Oscar-Fernando Bedoya-Leyva
Universidad del Valle

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

XML PDF

References

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. M. Gendreau, J.-Y. Potvin, Handbook of Metaheuristics, 2010. DOI: https://doi.org/10.1007/978-1-4419-1665-5
  11. B. Kitchenham, S. Charters, Guidelines for performing Systematic Literature Reviews in Software Engineering, 2007.
  12. 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
  13. 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.
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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
  20. 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
  21. 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
  22. 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
  23. 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
  24. 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
  25. 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
  26. 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
  27. 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
  28. 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
  29. 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
  30. 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
  31. 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
  32. 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
  33. 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
  34. 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
  35. 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.

Similar Articles

1 2 3 > >> 

You may also start an advanced similarity search for this article.