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

Standard

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

Harvard

APA

Vancouver

Author

Cohen, David ; Jeavons, Peter. / The power of propagation : when GAC is enough. In: Constraints. 2017 ; Vol. 22. pp. 3-23.

BibTeX

@article{d7aaa8f12f1a450ba199910186e94f8c,
title = "The power of propagation: when GAC is enough",
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.",
author = "David Cohen and Peter Jeavons",
year = "2017",
month = jan,
doi = "10.1007/s10601-016-9251-0",
language = "English",
volume = "22",
pages = "3--23",
journal = "Constraints",
issn = "1572-9354",
publisher = "Springer Netherlands",

}

RIS

TY - JOUR

T1 - The power of propagation

T2 - when GAC is enough

AU - Cohen, David

AU - Jeavons, Peter

PY - 2017/1

Y1 - 2017/1

N2 - 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.

AB - 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.

U2 - 10.1007/s10601-016-9251-0

DO - 10.1007/s10601-016-9251-0

M3 - Article

VL - 22

SP - 3

EP - 23

JO - Constraints

JF - Constraints

SN - 1572-9354

ER -