When do bounds and domain propagation lead to the same search space?
AuthorSchulte, C; Stuckey, PJ
Source TitleACM Transactions on Programming Languages and Systems
PublisherASSOC COMPUTING MACHINERY
University of Melbourne Author/sStuckey, Peter
AffiliationComputer Science and Software Engineering
Document TypeJournal Article
CitationsSchulte, C. & Stuckey, P. J. (2005). When do bounds and domain propagation lead to the same search space?. ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 27 (3), pp.388-425. https://doi.org/10.1145/1065887.1065889.
Access StatusThis item is currently not available from this repository
This article explores the question of when two propagation-based constraint systems have the same behavior, in terms of search space. We categorize the behavior of domain and bounds propagators for primitive constraints, and provide theorems that allow us to determine propagation behaviors for conjunctions of constraints. We then show how we can use this to analyze 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.
KeywordsComputer Software; Information Systems
- Click on "Export Reference in RIS Format" and choose "open with... Endnote".
- Click on "Export Reference in RIS Format". Login to Refworks, go to References => Import References