The power of propagation: when GAC is enough
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...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Published: |
Springer US
2016
|
| _version_ | 1826280674171027456 |
|---|---|
| author | Cohen, D Jeavons, P |
| author_facet | Cohen, D Jeavons, P |
| author_sort | Cohen, D |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T00:17:14Z |
| format | Journal article |
| id | oxford-uuid:7b465749-3e49-46d4-a56a-a7d384bfa04e |
| institution | University of Oxford |
| last_indexed | 2024-03-07T00:17:14Z |
| publishDate | 2016 |
| publisher | Springer US |
| record_format | dspace |
| spelling | oxford-uuid:7b465749-3e49-46d4-a56a-a7d384bfa04e2022-03-26T20:49:31ZThe power of propagation: when GAC is enoughJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:7b465749-3e49-46d4-a56a-a7d384bfa04eSymplectic Elements at OxfordSpringer US2016Cohen, DJeavons, PConsiderable 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. |
| spellingShingle | Cohen, D Jeavons, P The power of propagation: when GAC is enough |
| title | The power of propagation: when GAC is enough |
| title_full | The power of propagation: when GAC is enough |
| title_fullStr | The power of propagation: when GAC is enough |
| title_full_unstemmed | The power of propagation: when GAC is enough |
| title_short | The power of propagation: when GAC is enough |
| title_sort | power of propagation when gac is enough |
| work_keys_str_mv | AT cohend thepowerofpropagationwhengacisenough AT jeavonsp thepowerofpropagationwhengacisenough AT cohend powerofpropagationwhengacisenough AT jeavonsp powerofpropagationwhengacisenough |