TY - GEN
T1 - Enumeration strategies for solving constraint satisfaction problems
AU - SOTO DE GIORGIS, RICARDO JAVIER
AU - CRAWFORD LABRIN, BRODERICK
AU - Olivares, Rodrigo
AU - Herrera, Rodrigo
AU - Johnson, Franklin
AU - Paredes, Fernando
PY - 2015/1/1
Y1 - 2015/1/1
N2 - 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.
AB - 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.
KW - Constraint programming
KW - Constraint satisfaction problems
KW - Enumeration strategies
KW - Heuristics
UR - http://www.scopus.com/inward/record.url?scp=84940922112&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-18476-0_18
DO - 10.1007/978-3-319-18476-0_18
M3 - Conference contribution
AN - SCOPUS:84940922112
SN - 9783319184753
T3 - Advances in Intelligent Systems and Computing
SP - 169
EP - 179
BT - Artificial Intelligence Perspectives and Applications - Proceedings of the 4th Computer Science On-line Conference 2015, CSOC 2015
A2 - Silhavy, Radek
A2 - Senkerik, Roman
A2 - Oplatkova, Zuzana Kominkova
A2 - Prokopova, Zdenka
A2 - Silhavy, Petr
PB - Springer Verlag
Y2 - 27 April 2015 through 30 April 2015
ER -