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 JAVIER SOTO DE GIORGIS, BRODERICK CRAWFORD LABRIN, Ignacio Figueroa, Rodrigo Olivares, Eduardo Olguin

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-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 contributionThe set covering problem solved by the Black Hole Algorithm
Original languageSpanish
Title of host publicationProceedings of the 11th Iberian Conference on Information Systems and Technologies, CISTI 2016
EditorsAlvaro Rocha, Luis Paulo Reis, Manuel Perez Cota, Ramiro Goncalves, Octavio Santana Suarez
PublisherIEEE Computer Society
ISBN (Electronic)9789899843462
DOIs
StatePublished - 25 Jul 2016
Event11th Iberian Conference on Information Systems and Technologies, CISTI 2016 - Gran Canaria, Spain
Duration: 15 Jun 201618 Jun 2016

Publication series

NameIberian Conference on Information Systems and Technologies, CISTI
Volume2016-July
ISSN (Print)2166-0727
ISSN (Electronic)2166-0735

Conference

Conference11th Iberian Conference on Information Systems and Technologies, CISTI 2016
CountrySpain
CityGran Canaria
Period15/06/1618/06/16

Fingerprint Dive into the research topics of 'The set covering problem solved by the Black Hole Algorithm'. Together they form a unique fingerprint.

Cite this