Solving the set covering problem with a binary black hole inspired algorithm

Álvaro Gómez Rubio; Broderick Crawford; Ricardo Soto; Eduardo Olguín; Sanjay Misra; Adrián Jaramillo; Sebastián Mansilla Villablanca; Juan Salas

doi:10.1007/978-3-319-42085-1_16

Solving the set covering problem with a binary black hole inspired algorithm

Álvaro Gómez Rubio, Broderick Crawford, Ricardo Soto, Eduardo Olguín, Sanjay Misra, Adrián Jaramillo, Sebastián Mansilla Villablanca, Juan Salas

SCHOOL OF COMPUTER ENGINEERING

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

4 Scopus citations

Abstract

There are multiple problems in several industries that can be solved with combinatorial optimization. In this sense, the Set Covering Problem is one of the most representative of them, being used in various branches of engineering and science, allowing find a set of solutions that meet the needs identified in the restrictions that have the lowest possible cost. This paper presents an algorithm inspired by binary black holes (BBH) to resolve known instances of SPC from the OR-Library. Also, it reproduces the behavior of black holes, using various operators to bring good solutions.

Original language	English
Title of host publication	Computational Science and Its Applications - 16th International Conference, ICCSA 2016, Proceedings
Editors	Bernady O. Apduhan, Beniamino Murgante, Sanjay Misra, David Taniar, Carmelo M. Torre, Ana Maria A.C. Rocha, Shangguang Wang, Osvaldo Gervasi, Elena Stankova
Publisher	Springer Verlag
Pages	207-219
Number of pages	13
ISBN (Print)	9783319420844
DOIs	https://doi.org/10.1007/978-3-319-42085-1_16
State	Published - 2016
Event	16th International Conference on Computational Science and Its Applications, ICCSA 2016 - Beijing, China Duration: 4 Jul 2016 → 7 Jul 2016

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9786
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	16th International Conference on Computational Science and Its Applications, ICCSA 2016
Country/Territory	China
City	Beijing
Period	4/07/16 → 7/07/16

Keywords

Binary black hole
Combinatorial optimization problem
Meta heuristics
Set Covering Problem

Access to Document

10.1007/978-3-319-42085-1_16

Cite this

Rubio, Á. G., Crawford, B., Soto, R., Olguín, E., Misra, S., Jaramillo, A., Villablanca, S. M., & Salas, J. (2016). Solving the set covering problem with a binary black hole inspired algorithm. In B. O. Apduhan, B. Murgante, S. Misra, D. Taniar, C. M. Torre, A. M. A. C. Rocha, S. Wang, O. Gervasi, & E. Stankova (Eds.), Computational Science and Its Applications - 16th International Conference, ICCSA 2016, Proceedings (pp. 207-219). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9786). Springer Verlag. https://doi.org/10.1007/978-3-319-42085-1_16

Rubio, Álvaro Gómez ; Crawford, Broderick ; Soto, Ricardo et al. / Solving the set covering problem with a binary black hole inspired algorithm. Computational Science and Its Applications - 16th International Conference, ICCSA 2016, Proceedings. editor / Bernady O. Apduhan ; Beniamino Murgante ; Sanjay Misra ; David Taniar ; Carmelo M. Torre ; Ana Maria A.C. Rocha ; Shangguang Wang ; Osvaldo Gervasi ; Elena Stankova. Springer Verlag, 2016. pp. 207-219 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{56a80bbc156747c2aae2c868691f3b79,

title = "Solving the set covering problem with a binary black hole inspired algorithm",

abstract = "There are multiple problems in several industries that can be solved with combinatorial optimization. In this sense, the Set Covering Problem is one of the most representative of them, being used in various branches of engineering and science, allowing find a set of solutions that meet the needs identified in the restrictions that have the lowest possible cost. This paper presents an algorithm inspired by binary black holes (BBH) to resolve known instances of SPC from the OR-Library. Also, it reproduces the behavior of black holes, using various operators to bring good solutions.",

keywords = "Binary black hole, Combinatorial optimization problem, Meta heuristics, Set Covering Problem",

author = "Rubio, {{\'A}lvaro G{\'o}mez} and Broderick Crawford and Ricardo Soto and Eduardo Olgu{\'i}n and Sanjay Misra and Adri{\'a}n Jaramillo and Villablanca, {Sebasti{\'a}n Mansilla} and Juan Salas",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 16th International Conference on Computational Science and Its Applications, ICCSA 2016 ; Conference date: 04-07-2016 Through 07-07-2016",

year = "2016",

doi = "10.1007/978-3-319-42085-1_16",

language = "English",

isbn = "9783319420844",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "207--219",

editor = "Apduhan, {Bernady O.} and Beniamino Murgante and Sanjay Misra and David Taniar and Torre, {Carmelo M.} and Rocha, {Ana Maria A.C.} and Shangguang Wang and Osvaldo Gervasi and Elena Stankova",

booktitle = "Computational Science and Its Applications - 16th International Conference, ICCSA 2016, Proceedings",

}

Rubio, ÁG, Crawford, B , Soto, R, Olguín, E, Misra, S, Jaramillo, A, Villablanca, SM & Salas, J 2016, Solving the set covering problem with a binary black hole inspired algorithm. in BO Apduhan, B Murgante, S Misra, D Taniar, CM Torre, AMAC Rocha, S Wang, O Gervasi & E Stankova (eds), Computational Science and Its Applications - 16th International Conference, ICCSA 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9786, Springer Verlag, pp. 207-219, 16th International Conference on Computational Science and Its Applications, ICCSA 2016, Beijing, China, 4/07/16. https://doi.org/10.1007/978-3-319-42085-1_16

Solving the set covering problem with a binary black hole inspired algorithm. / Rubio, Álvaro Gómez; Crawford, Broderick ; Soto, Ricardo et al.
Computational Science and Its Applications - 16th International Conference, ICCSA 2016, Proceedings. ed. / Bernady O. Apduhan; Beniamino Murgante; Sanjay Misra; David Taniar; Carmelo M. Torre; Ana Maria A.C. Rocha; Shangguang Wang; Osvaldo Gervasi; Elena Stankova. Springer Verlag, 2016. p. 207-219 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9786).

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

TY - GEN

T1 - Solving the set covering problem with a binary black hole inspired algorithm

AU - Rubio, Álvaro Gómez

AU - Crawford, Broderick

AU - Soto, Ricardo

AU - Olguín, Eduardo

AU - Misra, Sanjay

AU - Jaramillo, Adrián

AU - Villablanca, Sebastián Mansilla

AU - Salas, Juan

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2016.

PY - 2016

Y1 - 2016

N2 - There are multiple problems in several industries that can be solved with combinatorial optimization. In this sense, the Set Covering Problem is one of the most representative of them, being used in various branches of engineering and science, allowing find a set of solutions that meet the needs identified in the restrictions that have the lowest possible cost. This paper presents an algorithm inspired by binary black holes (BBH) to resolve known instances of SPC from the OR-Library. Also, it reproduces the behavior of black holes, using various operators to bring good solutions.

AB - There are multiple problems in several industries that can be solved with combinatorial optimization. In this sense, the Set Covering Problem is one of the most representative of them, being used in various branches of engineering and science, allowing find a set of solutions that meet the needs identified in the restrictions that have the lowest possible cost. This paper presents an algorithm inspired by binary black holes (BBH) to resolve known instances of SPC from the OR-Library. Also, it reproduces the behavior of black holes, using various operators to bring good solutions.

KW - Binary black hole

KW - Combinatorial optimization problem

KW - Meta heuristics

KW - Set Covering Problem

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

U2 - 10.1007/978-3-319-42085-1_16

DO - 10.1007/978-3-319-42085-1_16

M3 - Conference contribution

AN - SCOPUS:84978796141

SN - 9783319420844

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 207

EP - 219

BT - Computational Science and Its Applications - 16th International Conference, ICCSA 2016, Proceedings

A2 - Apduhan, Bernady O.

A2 - Murgante, Beniamino

A2 - Misra, Sanjay

A2 - Taniar, David

A2 - Torre, Carmelo M.

A2 - Rocha, Ana Maria A.C.

A2 - Wang, Shangguang

A2 - Gervasi, Osvaldo

A2 - Stankova, Elena

PB - Springer Verlag

T2 - 16th International Conference on Computational Science and Its Applications, ICCSA 2016

Y2 - 4 July 2016 through 7 July 2016

ER -

Rubio ÁG, Crawford B , Soto R, Olguín E, Misra S, Jaramillo A et al. Solving the set covering problem with a binary black hole inspired algorithm. In Apduhan BO, Murgante B, Misra S, Taniar D, Torre CM, Rocha AMAC, Wang S, Gervasi O, Stankova E, editors, Computational Science and Its Applications - 16th International Conference, ICCSA 2016, Proceedings. Springer Verlag. 2016. p. 207-219. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-42085-1_16

Solving the set covering problem with a binary black hole inspired algorithm

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this