@inproceedings{a0daa4f7be514d1f901798dd94d688dc,

title = "Global difference constraint propagation for finite domain solvers",

abstract = "Difference constraints of the form x - y ≤ d are well studied, with efficient algorithms for satisfaction and implication, because of their connection to shortest paths. Finite domain propagation algorithms however do not make use of these algorithms, and typically treat each difference constraint as a separate propagator. Propagation does guarantee completeness of solving but can be needlessly slow. In this paper we describe how to build a (bounds consistent) global propagator for difference constraints that treats them all simultaneously. SAT modulo theory solvers have included theory solvers for difference constraints for some time. While a theory solver for difference constraints gives the basis of a global difference constraint propagator, we show how the requirements on the propagator are quite different. We give experiments showing that treating difference constraints globally can substantially improve on the standard propagation approach.",

keywords = "Difference logic, Global constraints, Propagation",

author = "Thibaut Feydy and Andreas Schutt and Stuckey, {Peter J.}",

year = "2008",

month = dec,

day = "17",

doi = "10.1145/1389449.1389478",

language = "English",

isbn = "9781605581170",

series = "PPDP'08 - Proceedings of the 10th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming",

pages = "226--235",

booktitle = "PPDP'08 - Proceedings of the 10th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming",

note = "PPDP 2008: 10th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming ; Conference date: 15-07-2008 Through 17-07-2008",

}