Early and efficient identification of useless constraint propagation for alldifferent constraints

Xizhe Zhang, Jian Gao, Yizhi Lv, Weixiong Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 Scopus citations

Abstract

Constraint propagation and backtracking are two basic techniques for solving constraint satisfaction problems (CSPs). During the search for a solution, the variable and value pairs that do not belong to any solution can be discarded by constraint propagation to ensure generalized arc consistency to avoid the fruitless search. However, constraint propagation is frequently invoked with little effect on many CSPs. Much effort has been devoted to predicting when to invoke constraint propagation for solving a CSP. However, no effective approach has been developed for the alldifferent constraint. Here we present a novel theorem for identifying the edges in a value graph of the alldifferent constraint whose removal can lead to useless constraint propagation. We prove that if an alternating cycle exists for a prospectively removable edge that represents a variable-value assignment, the edge (and the assignment) can be discarded without constraint propagation. Based on this theorem, we developed a novel optimization technique for early detection of useless constraint propagation which can be incorporated in any existing algorithm for the alldifferent constraint. Our implementation of the new method achieved speedup by a factor of 1 to 5 over the state-of-art approaches on 93 benchmark problem instances in 8 domains. Besides, the new algorithm is scalable well and runs increasingly faster than the existing methods on larger problems.

Original languageEnglish
Title of host publicationProceedings of the 29th International Joint Conference on Artificial Intelligence, IJCAI 2020
EditorsChristian Bessiere
PublisherInternational Joint Conferences on Artificial Intelligence
Pages1126-1133
Number of pages8
ISBN (Electronic)9780999241165
StatePublished - 2020
Event29th International Joint Conference on Artificial Intelligence, IJCAI 2020 - Yokohama, Japan
Duration: Jan 1 2021 → …

Publication series

NameIJCAI International Joint Conference on Artificial Intelligence
Volume2021-January
ISSN (Print)1045-0823

Conference

Conference29th International Joint Conference on Artificial Intelligence, IJCAI 2020
Country/TerritoryJapan
CityYokohama
Period01/1/21 → …

Fingerprint

Dive into the research topics of 'Early and efficient identification of useless constraint propagation for alldifferent constraints'. Together they form a unique fingerprint.

Cite this