Finite domain bounds consistency revisited

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

doi:10.1007/11941439-9

Finite domain bounds consistency revisited

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

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-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 language	English
Title of host publication	AI 2006
Subtitle of host publication	Advances in Artificial Intelligence - 19th Australian Joint Conference on Artificial Intelligence, Proceedings
Publisher	Springer
Pages	49-58
Number of pages	10
ISBN (Print)	9783540497875
DOIs	https://doi.org/10.1007/11941439-9
Publication status	Published - 1 Dec 2006
Externally published	Yes
Event	19th Australian Joint Conference onArtificial Intelligence, AI 2006 - Hobart, TAS, Australia Duration: 4 Dec 2006 → 8 Dec 2006

Conference

Conference	19th Australian Joint Conference onArtificial Intelligence, AI 2006
Country/Territory	Australia
City	Hobart, TAS
Period	4/12/06 → 8/12/06

Access to Document

10.1007/11941439-9

Cite this

@inproceedings{e2064d96e9014803801857660dc858ea,

title = "Finite domain bounds consistency revisited",

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.",

author = "Choi, {C. W.} and W. Harvey and Lee, {J. H.M.} and Stuckey, {P. J.}",

year = "2006",

month = dec,

day = "1",

doi = "10.1007/11941439-9",

language = "English",

isbn = "9783540497875",

pages = "49--58",

booktitle = "AI 2006",

publisher = "Springer",

note = "19th Australian Joint Conference onArtificial Intelligence, AI 2006 ; Conference date: 04-12-2006 Through 08-12-2006",

}

Choi, CW, Harvey, W, Lee, JHM & Stuckey, PJ 2006, Finite domain bounds consistency revisited. in AI 2006: Advances in Artificial Intelligence - 19th Australian Joint Conference on Artificial Intelligence, Proceedings. Springer, pp. 49-58, 19th Australian Joint Conference onArtificial Intelligence, AI 2006, Hobart, TAS, Australia, 4/12/06. https://doi.org/10.1007/11941439-9

TY - GEN

T1 - Finite domain bounds consistency revisited

AU - Choi, C. W.

AU - Harvey, W.

AU - Lee, J. H.M.

AU - Stuckey, P. J.

PY - 2006/12/1

Y1 - 2006/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84886432803&partnerID=8YFLogxK

U2 - 10.1007/11941439-9

DO - 10.1007/11941439-9

M3 - Conference Paper

AN - SCOPUS:84886432803

SN - 9783540497875

SP - 49

EP - 58

BT - AI 2006

PB - Springer

T2 - 19th Australian Joint Conference onArtificial Intelligence, AI 2006

Y2 - 4 December 2006 through 8 December 2006

ER -

Finite domain bounds consistency revisited

Abstract

Conference

Access to Document

Other files and links

Cite this