# A Meta-Optimization Approach to Solve the Set Covering Problem

## Un Enfoque de Meta-Optimización para Resolver el Problema de Cobertura de Conjunto

### Abstract (en_US)

**Context**: In the industry the resources are increasingly scarce. For this reason, we must make a good

use of it. Being the optimization tools, a good alternative that it is necessary to bear in mind. A realworld

problem is the facilities location being the Set Covering Problem, one of the most used models.

Our interest, it is to find solution alternatives to this problem of the real-world using metaheuristics.

**Method**: One of the main problems which we turn out to be faced on having used metaheuristic is the

difficulty of realizing a correct parametrization with the purpose to find good solutions. This is not an

easy task, for which our proposal is to use a metaheuristic that allows to provide good parameters to

another metaheuristics that will be responsible for resolving the Set Covering Problem.

**Results**: To prove our proposal, we use the set of 65 instances of OR-Library which also was compared

with other recent algorithms, used to solve the Set Covering Problem.

**Conclusions**: Our proposal has proved to be very effective able to produce solutions of good quality

avoiding also have to invest large amounts of time in the parametrization of the metaheuristic responsible

for resolving the problem.

### Abstract (es_ES)

**Contexto**: En la industria los recursos son cada vez más escasos. Por esta razón debemos hacer un buen uso de ellos.Siendo las herramientas de optimización una buena alternativa que se debe tener presente. Un problema del mundo real lo contituye la ubicación de instalaciones siendo el Problema de Cobertura de Conjuntos uno de los modelos más utilizados. Nuestro interés, es encontrar alternativas de solución a este problema de la vida-real utilizando metaheuristicas.

**Método**: Uno de los principales problemas a que nos vemos enfrentados al utilizar metaheurísticas es la dificultad de realizar una correcta parametrización con el objetivo de encontrar buenas soluciones. Esta no es una tarea fácil, para lo cual nuestra propuesta es utilizar una metaheurística que permita proporcionar buenos parametros a otra metaheurstica que será la encargada de resolver el Problema de Cobertura de Conjuntos.

**Resultados**: Para probar nuestra propuesta, utilizamos el set de 65 instancias de OR-Library el cual además fue comparado con otros recientes algoritmos utilizados para resolver el Problema de Cobertura de Conjuntos.

**Conclusiones**: Nuestra propuesta a demostrado ser muy efectiva logrando producir soluciones de buena calidad evitando además que se tenga que invertir gran cantidad de tiempo en la parametrización de la metaheurística encargada de resolver el problema.

### Downloads

### References

C. Ansótegui, M. Sellmann, and K. Tierney. A gender-based genetic algorithm for the automatic configuration of algorithms. In International Conference on Principles and Practice of Constraint Programming, pages 142–157. Springer, 2009.

S. Balaji and N. Revathi. A new approach for solving set covering problem using jumping particle swarm

optimization method. Natural Computing, 15(3):503–517, 2016.

M. Birattari and M. Dorigo. The problem of tuning metaheuristics as seen from a machine learning perspective. 2004.

B. Crawford, R. Soto, G. Astorga, J. García, C. Castro, and F. Paredes. Putting continuous metaheuristics to work in binary search spaces. Complexity, 2017, 2017.

B. Crawford, R. Soto, N. Berríos, F. Johnson, F. Paredes, C. Castro, and E. Norero. A binary cat swarm optimization algorithm for the non-unicost set covering problem. Mathematical Problems in Engineering, 2015,

B. Crawford, R. Soto, R. Cuesta, and F. Paredes. Application of the artificial bee colony algorithm for solving

the set covering problem. The Scientific World Journal, 2014(189164):1–8, April 2014.

B. Crawford, R. Soto, E. Monfroy, G. Astorga, J. Garc´ıa, and E. Cortes. A meta-optimization approach for

covering problems in facility location. In Workshop on Engineering Applications, pages 565–578. Springer,

B. Crawford, R. Soto, M. Olivares-Suárez, and F. Paredes. A binary firefly algorithm for the set covering problem. In 3rd Computer Science On-line Conference 2014 (CSOC 2014), volume 285 of Advances in Intelligent Systems and Computing, pages 65–73. Springer International Publishing, 2014.

B. Crawford, R. Soto, M. Olivares-Surez, F. Paredes, and F. Johnson. Binary firefly algorithm for the set covering problem. In 2014 9th Iberian Conference on Information Systems and Technologies (CISTI), pages 1–5, June 2014.

B. Crawford, R. Soto, W. Palma, F. Johnson, F. Paredes, and E. Olguín. A 2-level approach for the set covering problem: Parameter tuning of artificial bee colony algorithm by using genetic algorithm. In Y. Tan, Y. Shi,and C. Coello, editors, Advances in Swarm Intelligence, volume 8794, pages 189–196. Springer International Publishing, 2014.

B. Crawford, R. Soto, C. Peña, W. Palma, F. Johnson, and F. Paredes. Solving the set covering problem with a shuffled frog leaping algorithm. In 7th Asian Conference, ACIIDS 2015, Bali, Indonesia, March 23-25, 2015, Proceedings, Part II, volume 9012 of Lecture Notes in Computer Science, pages 41–50. Springer International Publishing, 2015.

B. Crawford, C. Valenzuela, R. Soto, E. Monfroy, and F. Paredes. Parameter tuning of metaheuristics using

metaheuristics. Advanced Science Letters, 19(12):3556–3559, 2013.

R. Cuesta, B. Crawford, R. Soto, and F. Paredes. An artificial bee colony algorithm for the set covering problem. In 3rd Computer Science On-line Conference 2014 (CSOC 2014), volume 285 of Advances in Intelligent Systems and Computing, pages 53–63. Springer International Publishing, 2014.

T. Drezner, Z. Drezner, and Z. Goldstein. A stochastic gradual cover location problem. Naval Research Logistics (NRL), 57(4):367–372, 2010.

G. Franceschini and S. Macchietto. Model-based design of experiments for parameter precision: State of the art. Chemical Engineering Science, 63(19):4846–4872, 2008.

J. García, B. Crawford, R. Soto, C. Carlos, and F. Paredes. A k-means binarization framework applied to

multidimensional knapsack problem. Applied Intelligence, pages 1–24, 2017.

J. García, B. Crawford, R. Soto, and P. García. A multi dynamic binary black hole algorithm applied to set

covering problem. In International Conference on Harmony Search Algorithm, pages 42–51. Springer, 2017.

J. J. Grefenstette. Optimization of control parameters for genetic algorithms. IEEE Transactions on systems, man, and cybernetics, 16(1):122–128, 1986.

D. Karaboga. An idea based on honey bee swarm for numerical optimization. Technical report, Technical

report-tr06, Erciyes university, engineering faculty, computer engineering department, 2005.

D. Karaboga. An idea based on honey bee swarm for numerical optimization. Technical Report TR06. Computer Engineering Department, Erciyes University, Turkey, 2005.

D. Karaboga and B. Basturk. A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. Journal Global Optimization, 39(3):459–471, 2007.

D. Karaboga, B. Gorkemli, C. Ozturk, and N. Karaboga. A comprehensive survey: artificial bee colony (ABC) algorithm and applications. Artificial Intelligence Review, 42(3):21–57, 2014.

M. López-Ibánez, J. Dubois-Lacoste, L. P. Cáceres, M. Birattari, and T. Sttzle. The irace package: Iterated

racing for automatic algorithm configuration. Operations Research Perspectives, 3:43 – 58, 2016.

Y. Lu and F. J. Vasko. An or practitioner’s solution approach for the set covering problem. International Journal of Applied Metaheuristic Computing (IJAMC), 6(4):1–13, 2015.

H. B. Mann and D. R. Whitney. On a test of whether one of two random variables is stochastically larger than the other. The annals of mathematical statistics, pages 50–60, 1947.

L. Santana, E. Ramiro, and J. d. J. Romero Carvajal. A hybrid column generation and clustering approach to the school bus routing problem with time windows. Ingeniería, 20(1):101–117, 2015.

D. Schilling, V. Jayaraman, and R. Barkhi. A review of covering problem in facility location. Location Science, Vol. 1(1):25–55, 1993.

B. Senthilkumar, T. Kannan, and R. Madesh. Optimization of flux-cored arc welding process parameters by

using genetic algorithm. The International Journal of Advanced Manufacturing Technology, 93(1-4):35–41,2017.

H. Shah-Hosseini. Intelligent water drops algorithm: A new optimization method for solving the multiple

knapsack problem. International Journal of Intelligent Computing and Cybernetics, 1(2):193–212, 2008.

S. S. Shapiro and M. B. Wilk. An analysis of variance test for normality (complete samples). Biometrika,

(3/4):591–611, 1965.

A. Singh. An artificial bee colony algorithm for the leaf-constrained minimum spanning tree problem. Applied Soft Computing, 9(2):625–631, 2009.

R. Soto, B. Crawford, A.Mu˜noz, F. Johnson, and F. Paredes. Pre-processing, repairing and transfer functions can help binary electromagnetism-like algorithms. In Artificial Intelligence Perspectives and Applications, volume 347 of Advances in Intelligent Systems and Computing, pages 89–97. Springer International Publishing, 2015.

R. Soto, B. Crawford, R. Olivares, J. Barraza, I. Figueroa, F. Johnson, F. Paredes, and E. Olgu´ın. Solving the non-unicost set covering problem by using cuckoo search and black hole optimization. Natural Computing,

pages 1–17, 2017.

C. Toregas, R. Swain, C. ReVelle, and L. Bergman. The location of emergency service facilities. Operations

Research, 19(6):1363–1373, 1971.

*Ingeniería*,

*23*(3). https://doi.org/10.14483/23448393.13247

From the edition of the V23N3 of year 2018 forward, the Creative Commons License "Attribution-Non-Commercial - No Derivative Works " is changed to the following:

**Attribution - Non-Commercial - Share the same**: this license allows others to distribute, remix, retouch, and create from your work in a non-commercial way, as long as they give you credit and license their new creations under the same conditions.