A beam-search approach to the set covering problem

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-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 languageEnglish
Title of host publicationArtificial Intelligence Perspectives in Intelligent Systems - Proceedings of 5th Computer Science On-line Conference, CSOC 2016
EditorsRadek Silhavy, Roman Senkerik, Zuzana Kominkova Oplatkova, Petr Silhavy, Zdenka Prokopova
PublisherSpringer Verlag
Pages395-402
Number of pages8
ISBN (Print)9783319336237
DOIs
StatePublished - 1 Jan 2016
Event5th Computer Science On-line Conference, CSOC 2016 - Prague, Czech Republic
Duration: 27 Apr 201630 Apr 2016

Publication series

NameAdvances in Intelligent Systems and Computing
Volume464
ISSN (Print)2194-5357

Conference

Conference5th Computer Science On-line Conference, CSOC 2016
CountryCzech Republic
CityPrague
Period27/04/1630/04/16

Keywords

  • Beam search
  • Branch-and-Bound
  • Greedy
  • SCP

Fingerprint Dive into the research topics of 'A beam-search approach to the set covering problem'. Together they form a unique fingerprint.

Cite this