Finite domain bounds consistency revisited

C. W. Choi, W. Harvey, J. H.M. Lee, P. J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

44 Citations (Scopus)

Abstract

A widely adopted approach to solving constraint satisfaction problems combines systematic tree search with constraint propagation for pruning the search space. Constraint propagation is performed by propagators implementing a certain notion of consistency. Bounds consistency is the method of choice for building propagators for arithmetic constraints and several global constraints in the finite integer domain. However, there has been some confusion in the definition of bounds consistency and of bounds propagators. We clarify the differences among the three commonly used notions of bounds consistency in the literature. This serves as a reference for implementations of bounds propagators by defining (for the first time) the a priori behavior of bounds propagators on arbitrary constraints.

Original languageEnglish
Title of host publicationAI 2006
Subtitle of host publicationAdvances in Artificial Intelligence - 19th Australian Joint Conference on Artificial Intelligence, Proceedings
PublisherSpringer
Pages49-58
Number of pages10
ISBN (Print)9783540497875
DOIs
Publication statusPublished - 1 Dec 2006
Externally publishedYes
Event19th Australian Joint Conference onArtificial Intelligence, AI 2006 - Hobart, TAS, Australia
Duration: 4 Dec 20068 Dec 2006

Conference

Conference19th Australian Joint Conference onArtificial Intelligence, AI 2006
Country/TerritoryAustralia
CityHobart, TAS
Period4/12/068/12/06

Cite this