The Power of Propagation: When GAC is Enough. / Cohen, David; Jeavons, Peter.

2016. Paper presented at CP2016. The 22nd International Conference on Principle and Practice of Constraint Programming, Toulouse, France.

Research output: Contribution to conferencePaperpeer-review

Forthcoming

Documents

  • CP_2016_paper_19

    Accepted author manuscript, 682 KB, PDF document

    Licence: Not specified

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 Sep 20169 Sep 2016

Conference

ConferenceCP2016. The 22nd International Conference on Principle and Practice of Constraint Programming
CountryFrance
CityToulouse
Period6/09/169/09/16
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 26545345