A beam-search approach to the set covering problem

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

Resultado de la investigación: Capítulo del libro/informe/acta de congresoContribución a la conferenciarevisión exhaustiva

1 Cita (Scopus)

Resumen

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.

Idioma originalInglés
Título de la publicación alojadaArtificial Intelligence Perspectives in Intelligent Systems - Proceedings of 5th Computer Science On-line Conference, CSOC 2016
EditoresRadek Silhavy, Roman Senkerik, Zuzana Kominkova Oplatkova, Petr Silhavy, Zdenka Prokopova
EditorialSpringer Verlag
Páginas395-402
Número de páginas8
ISBN (versión impresa)9783319336237
DOI
EstadoPublicada - 2016
Publicado de forma externa
Evento5th Computer Science On-line Conference, CSOC 2016 - Prague, República Checa
Duración: 27 abr. 201630 abr. 2016

Serie de la publicación

NombreAdvances in Intelligent Systems and Computing
Volumen464
ISSN (versión impresa)2194-5357

Conferencia

Conferencia5th Computer Science On-line Conference, CSOC 2016
País/TerritorioRepública Checa
CiudadPrague
Período27/04/1630/04/16

Huella

Profundice en los temas de investigación de 'A beam-search approach to the set covering problem'. En conjunto forman una huella única.

Citar esto