A beam-search approach to the set covering problem
Autor
Reyes V.
Araya I.
Crawford B.
Soto R.
Olguín E.
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. © Springer International Publishing Switzerland 2016.
Colecciones
Ítems relacionados
Mostrando ítems relacionados por Título, autor o materia.
-
Conference Paper
An artificial fish swarm optimization algorithm to solve set covering problem (2020)
Crawford B.; Soto R.; Olguín E.; Villablanca S.M.; Rubio Á.G.; Jaramillo A.; Salas J. (Springer Verlag, 2016) -
Conference Paper
A black hole algorithm for solving the set covering problem (2020)
Soto R.; Crawford B.; Figueroa I.; Niklander S.; Olguín E. (Springer Verlag, 2016) -
Conference Paper
Automatic triggering of constraint propagation (2020)
Monfroy E.; Crawford B.; Soto R. (2013)