TY - JOUR
T1 - Arc consistency during search
AU - Likitvivatanavong, Chavalit
AU - Zhang, Yuanlin
AU - Shannon, Scott
AU - Bowen, James
AU - Freuder, Eugene C.
N1 - Funding Information:
★The second author is supported by Science Foundation Ireland (Grant Numbers 05/IN/I886 and 10/IN.1/I3032). Part of this work was created while the second author visited Nantes in 2010 sponsored by CNRS (INS2I).
PY - 2007
Y1 - 2007
N2 - Enforcing arc consistency (AC) during search has proven to be a very effective method in solving Constraint Satisfaction Problems and it has been widely-used in many Constraint Programming systems. Although much effort has been made to design efficient standalone AC algorithms, there is no systematic study on how to efficiently enforce AC during search, as far as we know. The significance of the latter is clear given the fact that AC will be enforced millions of times in solving hard problems. In this paper, we propose a framework for enforcing AC during search (ACS) and complexity measurements of ACS algorithms. Based on this framework, several ACS algorithms are designed to take advantage of the residual data left in the data structures by the previous invocation(s) of ACS. The algorithms vary in the worst-case time and space complexity and other complexity measurements. Empirical study shows that some of the new ACS algorithms perform better than the conventional implementation of AC algorithms in a search procedure.
AB - Enforcing arc consistency (AC) during search has proven to be a very effective method in solving Constraint Satisfaction Problems and it has been widely-used in many Constraint Programming systems. Although much effort has been made to design efficient standalone AC algorithms, there is no systematic study on how to efficiently enforce AC during search, as far as we know. The significance of the latter is clear given the fact that AC will be enforced millions of times in solving hard problems. In this paper, we propose a framework for enforcing AC during search (ACS) and complexity measurements of ACS algorithms. Based on this framework, several ACS algorithms are designed to take advantage of the residual data left in the data structures by the previous invocation(s) of ACS. The algorithms vary in the worst-case time and space complexity and other complexity measurements. Empirical study shows that some of the new ACS algorithms perform better than the conventional implementation of AC algorithms in a search procedure.
UR - http://www.scopus.com/inward/record.url?scp=72749087272&partnerID=8YFLogxK
M3 - Conference article
AN - SCOPUS:72749087272
SN - 1045-0823
SP - 137
EP - 142
JO - IJCAI International Joint Conference on Artificial Intelligence
JF - IJCAI International Joint Conference on Artificial Intelligence
T2 - 20th International Joint Conference on Artificial Intelligence, IJCAI 2007
Y2 - 6 January 2007 through 12 January 2007
ER -