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.
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 language | English |
|---|---|
| Number of pages | 15 |
| Publication status | Accepted/In press - 6 Jun 2016 |
| Event | CP2016. The 22nd International Conference on Principle and Practice of Constraint Programming - Toulouse, France Duration: 6 Sept 2016 → 9 Sept 2016 |
Conference
| Conference | CP2016. The 22nd International Conference on Principle and Practice of Constraint Programming |
|---|---|
| Country/Territory | France |
| City | Toulouse |
| Period | 6/09/16 → 9/09/16 |