El Problema de Cobertura de Conjuntos solucionado por el Algoritmo del Agujero Negro

Ricardo Soto; Broderick Crawford; Ignacio Figueroa; Rodrigo Olivares; Eduardo Olguin

doi:10.1109/CISTI.2016.7521538

El Problema de Cobertura de Conjuntos solucionado por el Algoritmo del Agujero Negro

Translated title of the contribution: The set covering problem solved by the Black Hole Algorithm

Ricardo Soto, Broderick Crawford, Ignacio Figueroa, Rodrigo Olivares, Eduardo Olguin

SCHOOL OF COMPUTER ENGINEERING

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Abstract

The Set Covering Problem is a classical problem in combinatorial optimization that belongs to the Karp's 21 NP-hard problems, with many practical applications. In this paper, an approach based on Black Hole Algorithm is proposed to solve this problem. The black hole algorithm is a metaheuristic that is inspired by nature, especially by the black hole phenomenon in space. To improve the performance of metaheuristics are used repairing operator, which those solutions that violate the constraints, preprocessing accelerate the resolution of the problem, and transfer function and discretization function to adapts the solutions to a binary domains. We report interesting and competitive experimental results on a set of 45 instances preprocessed the Set Covering Problem.

Translated title of the contribution	The set covering problem solved by the Black Hole Algorithm
Original language	Spanish
Title of host publication	Proceedings of the 11th Iberian Conference on Information Systems and Technologies, CISTI 2016
Editors	Alvaro Rocha, Luis Paulo Reis, Manuel Perez Cota, Ramiro Goncalves, Octavio Santana Suarez
Publisher	IEEE Computer Society
ISBN (Electronic)	9789899843462
DOIs	https://doi.org/10.1109/CISTI.2016.7521538
State	Published - 25 Jul 2016
Event	11th Iberian Conference on Information Systems and Technologies, CISTI 2016 - Gran Canaria, Spain Duration: 15 Jun 2016 → 18 Jun 2016

Publication series

Name	Iberian Conference on Information Systems and Technologies, CISTI
Volume	2016-July
ISSN (Print)	2166-0727
ISSN (Electronic)	2166-0735

Conference

Conference	11th Iberian Conference on Information Systems and Technologies, CISTI 2016
Country/Territory	Spain
City	Gran Canaria
Period	15/06/16 → 18/06/16

Access to Document

10.1109/CISTI.2016.7521538

Cite this

Soto, R., Crawford, B., Figueroa, I., Olivares, R., & Olguin, E. (2016). El Problema de Cobertura de Conjuntos solucionado por el Algoritmo del Agujero Negro. In A. Rocha, L. P. Reis, M. P. Cota, R. Goncalves, & O. S. Suarez (Eds.), Proceedings of the 11th Iberian Conference on Information Systems and Technologies, CISTI 2016 Article 7521538 (Iberian Conference on Information Systems and Technologies, CISTI; Vol. 2016-July). IEEE Computer Society. https://doi.org/10.1109/CISTI.2016.7521538

Soto, Ricardo ; Crawford, Broderick ; Figueroa, Ignacio et al. / El Problema de Cobertura de Conjuntos solucionado por el Algoritmo del Agujero Negro. Proceedings of the 11th Iberian Conference on Information Systems and Technologies, CISTI 2016. editor / Alvaro Rocha ; Luis Paulo Reis ; Manuel Perez Cota ; Ramiro Goncalves ; Octavio Santana Suarez. IEEE Computer Society, 2016. (Iberian Conference on Information Systems and Technologies, CISTI).

@inproceedings{f8c896b5df064d11acde6094ae2fabdc,

title = "El Problema de Cobertura de Conjuntos solucionado por el Algoritmo del Agujero Negro",

abstract = "The Set Covering Problem is a classical problem in combinatorial optimization that belongs to the Karp's 21 NP-hard problems, with many practical applications. In this paper, an approach based on Black Hole Algorithm is proposed to solve this problem. The black hole algorithm is a metaheuristic that is inspired by nature, especially by the black hole phenomenon in space. To improve the performance of metaheuristics are used repairing operator, which those solutions that violate the constraints, preprocessing accelerate the resolution of the problem, and transfer function and discretization function to adapts the solutions to a binary domains. We report interesting and competitive experimental results on a set of 45 instances preprocessed the Set Covering Problem.",

keywords = "Black hole algorithm, optimization problem, set covering problem",

author = "Ricardo Soto and Broderick Crawford and Ignacio Figueroa and Rodrigo Olivares and Eduardo Olguin",

note = "Publisher Copyright: {\textcopyright} 2016 AISTI.; 11th Iberian Conference on Information Systems and Technologies, CISTI 2016 ; Conference date: 15-06-2016 Through 18-06-2016",

year = "2016",

month = jul,

day = "25",

doi = "10.1109/CISTI.2016.7521538",

language = "Spanish",

series = "Iberian Conference on Information Systems and Technologies, CISTI",

publisher = "IEEE Computer Society",

editor = "Alvaro Rocha and Reis, {Luis Paulo} and Cota, {Manuel Perez} and Ramiro Goncalves and Suarez, {Octavio Santana}",

booktitle = "Proceedings of the 11th Iberian Conference on Information Systems and Technologies, CISTI 2016",

}

Soto, R , Crawford, B, Figueroa, I, Olivares, R & Olguin, E 2016, El Problema de Cobertura de Conjuntos solucionado por el Algoritmo del Agujero Negro. in A Rocha, LP Reis, MP Cota, R Goncalves & OS Suarez (eds), Proceedings of the 11th Iberian Conference on Information Systems and Technologies, CISTI 2016., 7521538, Iberian Conference on Information Systems and Technologies, CISTI, vol. 2016-July, IEEE Computer Society, 11th Iberian Conference on Information Systems and Technologies, CISTI 2016, Gran Canaria, Spain, 15/06/16. https://doi.org/10.1109/CISTI.2016.7521538

El Problema de Cobertura de Conjuntos solucionado por el Algoritmo del Agujero Negro. / Soto, Ricardo ; Crawford, Broderick; Figueroa, Ignacio et al.
Proceedings of the 11th Iberian Conference on Information Systems and Technologies, CISTI 2016. ed. / Alvaro Rocha; Luis Paulo Reis; Manuel Perez Cota; Ramiro Goncalves; Octavio Santana Suarez. IEEE Computer Society, 2016. 7521538 (Iberian Conference on Information Systems and Technologies, CISTI; Vol. 2016-July).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - El Problema de Cobertura de Conjuntos solucionado por el Algoritmo del Agujero Negro

AU - Soto, Ricardo

AU - Crawford, Broderick

AU - Figueroa, Ignacio

AU - Olivares, Rodrigo

AU - Olguin, Eduardo

PY - 2016/7/25

Y1 - 2016/7/25

N2 - The Set Covering Problem is a classical problem in combinatorial optimization that belongs to the Karp's 21 NP-hard problems, with many practical applications. In this paper, an approach based on Black Hole Algorithm is proposed to solve this problem. The black hole algorithm is a metaheuristic that is inspired by nature, especially by the black hole phenomenon in space. To improve the performance of metaheuristics are used repairing operator, which those solutions that violate the constraints, preprocessing accelerate the resolution of the problem, and transfer function and discretization function to adapts the solutions to a binary domains. We report interesting and competitive experimental results on a set of 45 instances preprocessed the Set Covering Problem.

AB - The Set Covering Problem is a classical problem in combinatorial optimization that belongs to the Karp's 21 NP-hard problems, with many practical applications. In this paper, an approach based on Black Hole Algorithm is proposed to solve this problem. The black hole algorithm is a metaheuristic that is inspired by nature, especially by the black hole phenomenon in space. To improve the performance of metaheuristics are used repairing operator, which those solutions that violate the constraints, preprocessing accelerate the resolution of the problem, and transfer function and discretization function to adapts the solutions to a binary domains. We report interesting and competitive experimental results on a set of 45 instances preprocessed the Set Covering Problem.

KW - Black hole algorithm

KW - optimization problem

KW - set covering problem

UR - http://www.scopus.com/inward/record.url?scp=84982153360&partnerID=8YFLogxK

U2 - 10.1109/CISTI.2016.7521538

DO - 10.1109/CISTI.2016.7521538

M3 - Conference contribution

AN - SCOPUS:84982153360

T3 - Iberian Conference on Information Systems and Technologies, CISTI

BT - Proceedings of the 11th Iberian Conference on Information Systems and Technologies, CISTI 2016

A2 - Rocha, Alvaro

A2 - Reis, Luis Paulo

A2 - Cota, Manuel Perez

A2 - Goncalves, Ramiro

A2 - Suarez, Octavio Santana

PB - IEEE Computer Society

T2 - 11th Iberian Conference on Information Systems and Technologies, CISTI 2016

Y2 - 15 June 2016 through 18 June 2016

ER -

Soto R , Crawford B, Figueroa I, Olivares R, Olguin E. El Problema de Cobertura de Conjuntos solucionado por el Algoritmo del Agujero Negro. In Rocha A, Reis LP, Cota MP, Goncalves R, Suarez OS, editors, Proceedings of the 11th Iberian Conference on Information Systems and Technologies, CISTI 2016. IEEE Computer Society. 2016. 7521538. (Iberian Conference on Information Systems and Technologies, CISTI). doi: 10.1109/CISTI.2016.7521538

El Problema de Cobertura de Conjuntos solucionado por el Algoritmo del Agujero Negro

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this