The power of propagation: when GAC is enough

David Cohen, Peter Jeavons

Research output: Contribution to journalArticlepeer-review

64 Downloads (Pure)

Abstract

Considerable effort in constraint programming has focused on the development of efficient propagators for individual constraints. In this paper, we consider the combined power of such propagators when applied to collections of more than one constraint. In particular we identify classes of constraint problems where such propagators can decide the existence of a solution on their own, without the need for any additional search. Sporadic examples of such classes have previously been identified, including classes based on restricting the structure of the problem, restricting the constraint types, and some hybrid examples. However, there has previously been no unifying approach which characterises all of these classes: structural, language-based and hybrid. In this paper we develop such a unifying approach and embed all the known classes into a common framework. We then use this framework to identify a further class of problems that can be solved by propagation alone.
Original languageEnglish
Pages (from-to)3-23
Number of pages21
JournalConstraints
Volume22
Early online date23 Aug 2016
DOIs
Publication statusPublished - Jan 2017

Cite this