A black hole algorithm for solving the set covering problem

Ricardo Soto; Broderick Crawford; Ignacio Figueroa; Stefanie Niklander; Eduardo Olguín

doi:10.1007/978-3-319-42007-3_72

A black hole algorithm for solving the set covering problem

Ricardo Soto, Broderick Crawford, Ignacio Figueroa, Stefanie Niklander, Eduardo Olguín

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 optimization benchmark with many industrial applications such as production planning, assembly line balancing, and crew scheduling among several others. In this work, we solve such a problem by employing a recent nature-inspired metaheuristic based on the black hole phenomena. The core of such a metaheuristic is enhanced with the incorporation of transfer functions and discretization methods to handle the binary nature of the problem. We illustrate encouraging experimental results, where the proposed approach is capable to reach various global optimums for a well-known instance set from the Beasley’s OR-Library.

Original language	English
Title of host publication	Trends in Applied Knowledge-Based Systems and Data Science - 29th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2016, Proceedings
Editors	Moonis Ali, Hamido Fujita, Jun Sasaki, Masaki Kurematsu, Ali Selamat
Publisher	Springer Verlag
Pages	855-861
Number of pages	7
ISBN (Print)	9783319420066
DOIs	https://doi.org/10.1007/978-3-319-42007-3_72
State	Published - 2016
Event	29th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2016 - Morioka, Japan Duration: 2 Aug 2016 → 4 Aug 2016

Publication series

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

Conference

Conference	29th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2016
Country/Territory	Japan
City	Morioka
Period	2/08/16 → 4/08/16

Keywords

Black Hole algorithm
Meta-heuristics
Set covering problem
Soft computing

Access to Document

10.1007/978-3-319-42007-3_72

Cite this

Soto, R., Crawford, B., Figueroa, I., Niklander, S., & Olguín, E. (2016). A black hole algorithm for solving the set covering problem. In M. Ali, H. Fujita, J. Sasaki, M. Kurematsu, & A. Selamat (Eds.), Trends in Applied Knowledge-Based Systems and Data Science - 29th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2016, Proceedings (pp. 855-861). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9799). Springer Verlag. https://doi.org/10.1007/978-3-319-42007-3_72

Soto, Ricardo ; Crawford, Broderick ; Figueroa, Ignacio et al. / A black hole algorithm for solving the set covering problem. Trends in Applied Knowledge-Based Systems and Data Science - 29th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2016, Proceedings. editor / Moonis Ali ; Hamido Fujita ; Jun Sasaki ; Masaki Kurematsu ; Ali Selamat. Springer Verlag, 2016. pp. 855-861 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{6a6c14a513c542669d5f7455f0bf48a2,

title = "A black hole algorithm for solving the set covering problem",

abstract = "The set covering problem is a classical optimization benchmark with many industrial applications such as production planning, assembly line balancing, and crew scheduling among several others. In this work, we solve such a problem by employing a recent nature-inspired metaheuristic based on the black hole phenomena. The core of such a metaheuristic is enhanced with the incorporation of transfer functions and discretization methods to handle the binary nature of the problem. We illustrate encouraging experimental results, where the proposed approach is capable to reach various global optimums for a well-known instance set from the Beasley{\textquoteright}s OR-Library.",

keywords = "Black Hole algorithm, Meta-heuristics, Set covering problem, Soft computing",

author = "Ricardo Soto and Broderick Crawford and Ignacio Figueroa and Stefanie Niklander and Eduardo Olgu{\'i}n",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 29th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2016 ; Conference date: 02-08-2016 Through 04-08-2016",

year = "2016",

doi = "10.1007/978-3-319-42007-3_72",

language = "English",

isbn = "9783319420066",

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

publisher = "Springer Verlag",

pages = "855--861",

editor = "Moonis Ali and Hamido Fujita and Jun Sasaki and Masaki Kurematsu and Ali Selamat",

booktitle = "Trends in Applied Knowledge-Based Systems and Data Science - 29th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2016, Proceedings",

}

Soto, R , Crawford, B, Figueroa, I, Niklander, S & Olguín, E 2016, A black hole algorithm for solving the set covering problem. in M Ali, H Fujita, J Sasaki, M Kurematsu & A Selamat (eds), Trends in Applied Knowledge-Based Systems and Data Science - 29th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2016, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9799, Springer Verlag, pp. 855-861, 29th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2016, Morioka, Japan, 2/08/16. https://doi.org/10.1007/978-3-319-42007-3_72

A black hole algorithm for solving the set covering problem. / Soto, Ricardo ; Crawford, Broderick; Figueroa, Ignacio et al.
Trends in Applied Knowledge-Based Systems and Data Science - 29th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2016, Proceedings. ed. / Moonis Ali; Hamido Fujita; Jun Sasaki; Masaki Kurematsu; Ali Selamat. Springer Verlag, 2016. p. 855-861 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9799).

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

TY - GEN

T1 - A black hole algorithm for solving the set covering problem

AU - Soto, Ricardo

AU - Crawford, Broderick

AU - Figueroa, Ignacio

AU - Niklander, Stefanie

AU - Olguín, Eduardo

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

PY - 2016

Y1 - 2016

N2 - The set covering problem is a classical optimization benchmark with many industrial applications such as production planning, assembly line balancing, and crew scheduling among several others. In this work, we solve such a problem by employing a recent nature-inspired metaheuristic based on the black hole phenomena. The core of such a metaheuristic is enhanced with the incorporation of transfer functions and discretization methods to handle the binary nature of the problem. We illustrate encouraging experimental results, where the proposed approach is capable to reach various global optimums for a well-known instance set from the Beasley’s OR-Library.

AB - The set covering problem is a classical optimization benchmark with many industrial applications such as production planning, assembly line balancing, and crew scheduling among several others. In this work, we solve such a problem by employing a recent nature-inspired metaheuristic based on the black hole phenomena. The core of such a metaheuristic is enhanced with the incorporation of transfer functions and discretization methods to handle the binary nature of the problem. We illustrate encouraging experimental results, where the proposed approach is capable to reach various global optimums for a well-known instance set from the Beasley’s OR-Library.

KW - Black Hole algorithm

KW - Meta-heuristics

KW - Set covering problem

KW - Soft computing

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

U2 - 10.1007/978-3-319-42007-3_72

DO - 10.1007/978-3-319-42007-3_72

M3 - Conference contribution

AN - SCOPUS:84978852411

SN - 9783319420066

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

SP - 855

EP - 861

BT - Trends in Applied Knowledge-Based Systems and Data Science - 29th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2016, Proceedings

A2 - Ali, Moonis

A2 - Fujita, Hamido

A2 - Sasaki, Jun

A2 - Kurematsu, Masaki

A2 - Selamat, Ali

PB - Springer Verlag

T2 - 29th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2016

Y2 - 2 August 2016 through 4 August 2016

ER -

Soto R , Crawford B, Figueroa I, Niklander S, Olguín E. A black hole algorithm for solving the set covering problem. In Ali M, Fujita H, Sasaki J, Kurematsu M, Selamat A, editors, Trends in Applied Knowledge-Based Systems and Data Science - 29th International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2016, Proceedings. Springer Verlag. 2016. p. 855-861. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-42007-3_72

A black hole algorithm for solving the set covering problem

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this