When Do Bounds and Domain Propagation Lead to the Same Search Space?
Christian Schulte, Peter J. Stuckey.
[pdf | ACM version | bibtex]
This paper explores the question of when two propagation-based constraint systems have the same behaviour, in terms of search space. We categorise the behaviour of domain and bounds propagators for primitive constraints, and provide theorems that allow us to determine propagation behaviours for conjunctions of constraints. We then show how we can use this to analyse CLP(FD) programs to determine when we can safely replace domain propagators by more efficient bounds propagators without increasing search space. Empirical evaluation shows that programs optimized by the analysis' results are considerably more efficient.
In: Transactions on Programming Languages and Systems 27(3), pages 388-425. ACM Press, May, 2005. DOI 10.1145/1065887.1065889.
Copyright ACM, 2005. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definite version was published as described above.