Title
Enumeration strategies for solving constraint satisfaction problems: A performance evaluation
Date Issued
01 January 2015
Access level
metadata only access
Resource Type
conference paper
Author(s)
Universidad Autónoma de Chile
Publisher(s)
Springer Verlag
Abstract
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.
Start page
169
End page
179
Volume
347
Language
English
OCDE Knowledge area
Sistemas de automatización, Sistemas de control
Ingeniería de sistemas y comunicaciones
Subjects
Scopus EID
2-s2.0-84940922112
Source
Advances in Intelligent Systems and Computing
ISSN of the container
21945357
ISBN of the container
9783319184753
Conference
4th Computer Science On-line Conference, CSOC 2015
Sponsor(s)
Comisión Nacional de Investigación Científica y Tecnológica 11130459, 1130455, 1140897
Sources of information:
Directorio de Producción Científica
Scopus