When do bounds and domain propagation lead to the same search space?

Christian Schulte, Peter J. Stuckey

Research output: Contribution to journalArticleResearchpeer-review

22 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)388-425
Number of pages38
JournalACM Transactions on Programming Languages and Systems
Volume27
Issue number3
DOIs
Publication statusPublished - 1 Dec 2005
Externally publishedYes

Keywords

  • Abstract interpretation
  • Bounds propagation
  • Constraint (logic) programming
  • Domain propagation
  • Finite domain constraints
  • Program analysis

Cite this