Enumeration strategies for solving constraint satisfaction problems: A performance evaluation

Ricardo Soto, Broderick Crawford, Rodrigo Olivares, Rodrigo Herrera, Franklin Johnson, Fernando Paredes

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

1 Cita (Scopus)

Resumen

Constraint programming allows to solve constraint satisfaction and optimization problems by building and then exploring a search tree of potential solutions. Potential solutions are generated by firstly selecting a variable and then a value from the given problem. The enumeration strategy is responsible for selecting the order in which those variables and values are selected to produce a potential solution. There exist different ways to perform this selection, and depending on the quality of this decision, the efficiency of the solving process may dramatically vary. A main concern in this context is that the behavior of the strategy is notably hard to predict. In this paper, we present a performance evaluation of 24 enumeration strategies for solving constraint satisfaction problems. Our goal is to provide new and interesting knowledge about the behavior of such strategies. To this end, we employ a set of wellknown benchmarks that collect general features that may be present on most constraint satisfaction and optimization problems. We believe this information will be useful to help users making better solving decisions when facing new problems.

Idioma originalInglés
Título de la publicación alojadaArtificial Intelligence Perspectives and Applications - Proceedings of the 4th Computer Science On-line Conference 2015, CSOC 2015
EditoresRadek Silhavy, Roman Senkerik, Zuzana Kominkova Oplatkova, Zdenka Prokopova, Petr Silhavy
EditorialSpringer Verlag
Páginas169-179
Número de páginas11
ISBN (versión impresa)9783319184753
DOI
EstadoPublicada - 2015
Publicado de forma externa
Evento4th Computer Science On-line Conference, CSOC 2015 - Zlin, República Checa
Duración: 27 abr. 201530 abr. 2015

Serie de la publicación

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

Conferencia

Conferencia4th Computer Science On-line Conference, CSOC 2015
País/TerritorioRepública Checa
CiudadZlin
Período27/04/1530/04/15

Huella

Profundice en los temas de investigación de 'Enumeration strategies for solving constraint satisfaction problems: A performance evaluation'. En conjunto forman una huella única.

Citar esto