The power of propagation : when GAC is enough. / Cohen, David; Jeavons, Peter.

In: Constraints, Vol. 22, 01.2017, p. 3-23.

Research output: Contribution to journalArticlepeer-review

Published

Documents

  • Accepted Manuscript

    Rights statement: This is the pre-editied version which seems to be open according to SPringer who charge 3,000 for full open access. This is allowed under their green access policy

    Accepted author manuscript, 821 KB, PDF document

    Licence: CC BY Show licence

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
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 27849948