A beam-search approach to the set covering problem

Victor Reyes; Ignacio Araya; Broderick Crawford; Ricardo Soto; Eduardo Olguín

doi:10.1007/978-3-319-33625-1_35

A beam-search approach to the set covering problem

Victor Reyes, Ignacio Araya, Broderick Crawford, Ricardo Soto, Eduardo Olguín

SCHOOL OF COMPUTER ENGINEERING

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

1 Scopus citations

Abstract

In this work we present a beam-search approach applied to the Set Covering Problem. The goal of this problem is to choose a subset of columns of minimal cost covering every row. Beam Search constructs a search tree by using a breadthfirst search strategy, however only a fixed number of nodes are kept and the rest are discarded. Even though original beam search has a deterministic nature, our proposal has some elements that makes it stochastic. This approach has been tested with a well-known set of 45 SCP benchmark instances from OR-Library showing promising results.

Original language	English
Title of host publication	Artificial Intelligence Perspectives in Intelligent Systems - Proceedings of 5th Computer Science On-line Conference, CSOC 2016
Editors	Radek Silhavy, Roman Senkerik, Zuzana Kominkova Oplatkova, Petr Silhavy, Zdenka Prokopova
Publisher	Springer Verlag
Pages	395-402
Number of pages	8
ISBN (Print)	9783319336237
DOIs	https://doi.org/10.1007/978-3-319-33625-1_35
State	Published - 2016
Event	5th Computer Science On-line Conference, CSOC 2016 - Prague, Czech Republic Duration: 27 Apr 2016 → 30 Apr 2016

Publication series

Name	Advances in Intelligent Systems and Computing
Volume	464
ISSN (Print)	2194-5357

Conference

Conference	5th Computer Science On-line Conference, CSOC 2016
Country/Territory	Czech Republic
City	Prague
Period	27/04/16 → 30/04/16

Keywords

Beam search
Branch-and-Bound
Greedy
SCP

Access to Document

10.1007/978-3-319-33625-1_35

Cite this

Reyes, V., Araya, I., Crawford, B., Soto, R., & Olguín, E. (2016). A beam-search approach to the set covering problem. In R. Silhavy, R. Senkerik, Z. K. Oplatkova, P. Silhavy, & Z. Prokopova (Eds.), Artificial Intelligence Perspectives in Intelligent Systems - Proceedings of 5th Computer Science On-line Conference, CSOC 2016 (pp. 395-402). (Advances in Intelligent Systems and Computing; Vol. 464). Springer Verlag. https://doi.org/10.1007/978-3-319-33625-1_35

Reyes, Victor ; Araya, Ignacio ; Crawford, Broderick et al. / A beam-search approach to the set covering problem. Artificial Intelligence Perspectives in Intelligent Systems - Proceedings of 5th Computer Science On-line Conference, CSOC 2016. editor / Radek Silhavy ; Roman Senkerik ; Zuzana Kominkova Oplatkova ; Petr Silhavy ; Zdenka Prokopova. Springer Verlag, 2016. pp. 395-402 (Advances in Intelligent Systems and Computing).

@inproceedings{a9eb3eaf01c84075b739815646a60e5e,

title = "A beam-search approach to the set covering problem",

abstract = "In this work we present a beam-search approach applied to the Set Covering Problem. The goal of this problem is to choose a subset of columns of minimal cost covering every row. Beam Search constructs a search tree by using a breadthfirst search strategy, however only a fixed number of nodes are kept and the rest are discarded. Even though original beam search has a deterministic nature, our proposal has some elements that makes it stochastic. This approach has been tested with a well-known set of 45 SCP benchmark instances from OR-Library showing promising results.",

keywords = "Beam search, Branch-and-Bound, Greedy, SCP",

author = "Victor Reyes and Ignacio Araya and Broderick Crawford and Ricardo Soto and Eduardo Olgu{\'i}n",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2016.; 5th Computer Science On-line Conference, CSOC 2016 ; Conference date: 27-04-2016 Through 30-04-2016",

year = "2016",

doi = "10.1007/978-3-319-33625-1_35",

language = "English",

isbn = "9783319336237",

series = "Advances in Intelligent Systems and Computing",

publisher = "Springer Verlag",

pages = "395--402",

editor = "Radek Silhavy and Roman Senkerik and Oplatkova, {Zuzana Kominkova} and Petr Silhavy and Zdenka Prokopova",

booktitle = "Artificial Intelligence Perspectives in Intelligent Systems - Proceedings of 5th Computer Science On-line Conference, CSOC 2016",

}

Reyes, V, Araya, I , Crawford, B , Soto, R & Olguín, E 2016, A beam-search approach to the set covering problem. in R Silhavy, R Senkerik, ZK Oplatkova, P Silhavy & Z Prokopova (eds), Artificial Intelligence Perspectives in Intelligent Systems - Proceedings of 5th Computer Science On-line Conference, CSOC 2016. Advances in Intelligent Systems and Computing, vol. 464, Springer Verlag, pp. 395-402, 5th Computer Science On-line Conference, CSOC 2016, Prague, Czech Republic, 27/04/16. https://doi.org/10.1007/978-3-319-33625-1_35

A beam-search approach to the set covering problem. / Reyes, Victor; Araya, Ignacio ; Crawford, Broderick et al.
Artificial Intelligence Perspectives in Intelligent Systems - Proceedings of 5th Computer Science On-line Conference, CSOC 2016. ed. / Radek Silhavy; Roman Senkerik; Zuzana Kominkova Oplatkova; Petr Silhavy; Zdenka Prokopova. Springer Verlag, 2016. p. 395-402 (Advances in Intelligent Systems and Computing; Vol. 464).

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

TY - GEN

T1 - A beam-search approach to the set covering problem

AU - Reyes, Victor

AU - Araya, Ignacio

AU - Crawford, Broderick

AU - Soto, Ricardo

AU - Olguín, Eduardo

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

PY - 2016

Y1 - 2016

N2 - In this work we present a beam-search approach applied to the Set Covering Problem. The goal of this problem is to choose a subset of columns of minimal cost covering every row. Beam Search constructs a search tree by using a breadthfirst search strategy, however only a fixed number of nodes are kept and the rest are discarded. Even though original beam search has a deterministic nature, our proposal has some elements that makes it stochastic. This approach has been tested with a well-known set of 45 SCP benchmark instances from OR-Library showing promising results.

AB - In this work we present a beam-search approach applied to the Set Covering Problem. The goal of this problem is to choose a subset of columns of minimal cost covering every row. Beam Search constructs a search tree by using a breadthfirst search strategy, however only a fixed number of nodes are kept and the rest are discarded. Even though original beam search has a deterministic nature, our proposal has some elements that makes it stochastic. This approach has been tested with a well-known set of 45 SCP benchmark instances from OR-Library showing promising results.

KW - Beam search

KW - Branch-and-Bound

KW - Greedy

KW - SCP

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

U2 - 10.1007/978-3-319-33625-1_35

DO - 10.1007/978-3-319-33625-1_35

M3 - Conference contribution

AN - SCOPUS:84964699789

SN - 9783319336237

T3 - Advances in Intelligent Systems and Computing

SP - 395

EP - 402

BT - Artificial Intelligence Perspectives in Intelligent Systems - Proceedings of 5th Computer Science On-line Conference, CSOC 2016

A2 - Silhavy, Radek

A2 - Senkerik, Roman

A2 - Oplatkova, Zuzana Kominkova

A2 - Silhavy, Petr

A2 - Prokopova, Zdenka

PB - Springer Verlag

T2 - 5th Computer Science On-line Conference, CSOC 2016

Y2 - 27 April 2016 through 30 April 2016

ER -

Reyes V, Araya I , Crawford B , Soto R, Olguín E. A beam-search approach to the set covering problem. In Silhavy R, Senkerik R, Oplatkova ZK, Silhavy P, Prokopova Z, editors, Artificial Intelligence Perspectives in Intelligent Systems - Proceedings of 5th Computer Science On-line Conference, CSOC 2016. Springer Verlag. 2016. p. 395-402. (Advances in Intelligent Systems and Computing). doi: 10.1007/978-3-319-33625-1_35

A beam-search approach to the set covering problem

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this