The Power of Propagation: When GAC is Enough

David Cohen, Peter Jeavons

Research output: Contribution to conferencePaperpeer-review

34 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 efficiently
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 novel classes of problems that can be solved by propagation
alone.
Original languageEnglish
Number of pages15
Publication statusAccepted/In press - 6 Jun 2016
EventCP2016. The 22nd International Conference on Principle and Practice of Constraint Programming - Toulouse, France
Duration: 6 Sept 20169 Sept 2016

Conference

ConferenceCP2016. The 22nd International Conference on Principle and Practice of Constraint Programming
Country/TerritoryFrance
CityToulouse
Period6/09/169/09/16

Cite this