Enumeration strategies for solving constraint satisfaction problems: A performance evaluation

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

doi:10.1007/978-3-319-18476-0_18

Enumeration strategies for solving constraint satisfaction problems: A performance evaluation

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

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.

Original language	English
Title of host publication	Artificial Intelligence Perspectives and Applications - Proceedings of the 4th Computer Science On-line Conference 2015, CSOC 2015
Editors	Radek Silhavy, Roman Senkerik, Zuzana Kominkova Oplatkova, Zdenka Prokopova, Petr Silhavy
Publisher	Springer Verlag
Pages	169-179
Number of pages	11
ISBN (Print)	9783319184753
DOIs	https://doi.org/10.1007/978-3-319-18476-0_18
State	Published - 2015
Externally published	Yes
Event	4th Computer Science On-line Conference, CSOC 2015 - Zlin, Czech Republic Duration: 27 Apr 2015 → 30 Apr 2015

Publication series

Name	Advances in Intelligent Systems and Computing
Volume	347
ISSN (Print)	2194-5357

Conference

Conference	4th Computer Science On-line Conference, CSOC 2015
Country/Territory	Czech Republic
City	Zlin
Period	27/04/15 → 30/04/15

Keywords

Constraint programming
Constraint satisfaction problems
Enumeration strategies
Heuristics

Access to Document

10.1007/978-3-319-18476-0_18

Cite this

Soto, R., Crawford, B., Olivares, R., Herrera, R., Johnson, F., & Paredes, F. (2015). Enumeration strategies for solving constraint satisfaction problems: A performance evaluation. In R. Silhavy, R. Senkerik, Z. K. Oplatkova, Z. Prokopova, & P. Silhavy (Eds.), Artificial Intelligence Perspectives and Applications - Proceedings of the 4th Computer Science On-line Conference 2015, CSOC 2015 (pp. 169-179). (Advances in Intelligent Systems and Computing; Vol. 347). Springer Verlag. https://doi.org/10.1007/978-3-319-18476-0_18

Soto, Ricardo ; Crawford, Broderick ; Olivares, Rodrigo et al. / Enumeration strategies for solving constraint satisfaction problems : A performance evaluation. Artificial Intelligence Perspectives and Applications - Proceedings of the 4th Computer Science On-line Conference 2015, CSOC 2015. editor / Radek Silhavy ; Roman Senkerik ; Zuzana Kominkova Oplatkova ; Zdenka Prokopova ; Petr Silhavy. Springer Verlag, 2015. pp. 169-179 (Advances in Intelligent Systems and Computing).

@inproceedings{2864ffcf51bc47ba84ecf25612c83629,

title = "Enumeration strategies for solving constraint satisfaction problems: A performance evaluation",

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.",

keywords = "Constraint programming, Constraint satisfaction problems, Enumeration strategies, Heuristics",

author = "Ricardo Soto and Broderick Crawford and Rodrigo Olivares and Rodrigo Herrera and Franklin Johnson and Fernando Paredes",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; null ; Conference date: 27-04-2015 Through 30-04-2015",

year = "2015",

doi = "10.1007/978-3-319-18476-0_18",

language = "English",

isbn = "9783319184753",

series = "Advances in Intelligent Systems and Computing",

publisher = "Springer Verlag",

pages = "169--179",

editor = "Radek Silhavy and Roman Senkerik and Oplatkova, {Zuzana Kominkova} and Zdenka Prokopova and Petr Silhavy",

booktitle = "Artificial Intelligence Perspectives and Applications - Proceedings of the 4th Computer Science On-line Conference 2015, CSOC 2015",

}

Soto, R , Crawford, B, Olivares, R, Herrera, R, Johnson, F & Paredes, F 2015, Enumeration strategies for solving constraint satisfaction problems: A performance evaluation. in R Silhavy, R Senkerik, ZK Oplatkova, Z Prokopova & P Silhavy (eds), Artificial Intelligence Perspectives and Applications - Proceedings of the 4th Computer Science On-line Conference 2015, CSOC 2015. Advances in Intelligent Systems and Computing, vol. 347, Springer Verlag, pp. 169-179, 4th Computer Science On-line Conference, CSOC 2015, Zlin, Czech Republic, 27/04/15. https://doi.org/10.1007/978-3-319-18476-0_18

Enumeration strategies for solving constraint satisfaction problems : A performance evaluation. / Soto, Ricardo ; Crawford, Broderick; Olivares, Rodrigo et al.

Artificial Intelligence Perspectives and Applications - Proceedings of the 4th Computer Science On-line Conference 2015, CSOC 2015. ed. / Radek Silhavy; Roman Senkerik; Zuzana Kominkova Oplatkova; Zdenka Prokopova; Petr Silhavy. Springer Verlag, 2015. p. 169-179 (Advances in Intelligent Systems and Computing; Vol. 347).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Enumeration strategies for solving constraint satisfaction problems

AU - Soto, Ricardo

AU - Crawford, Broderick

AU - Olivares, Rodrigo

AU - Herrera, Rodrigo

AU - Johnson, Franklin

AU - Paredes, Fernando

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2015.

PY - 2015

Y1 - 2015

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 -

Soto R , Crawford B, Olivares R, Herrera R, Johnson F, Paredes F. Enumeration strategies for solving constraint satisfaction problems: A performance evaluation. In Silhavy R, Senkerik R, Oplatkova ZK, Prokopova Z, Silhavy P, editors, Artificial Intelligence Perspectives and Applications - Proceedings of the 4th Computer Science On-line Conference 2015, CSOC 2015. Springer Verlag. 2015. p. 169-179. (Advances in Intelligent Systems and Computing). doi: 10.1007/978-3-319-18476-0_18

Enumeration strategies for solving constraint satisfaction problems: A performance evaluation

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this