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

45 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	Australian Joint Conference on Artificial Intelligence, AI 2006 - Hobart, Australia Duration: 4 Dec 2006 → 8 Dec 2006 Conference number: 19th

Conference

Conference	Australian Joint Conference on Artificial Intelligence, AI 2006
Abbreviated title	AI 2006
Country/Territory	Australia
City	Hobart
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",

address = "Switzerland",

note = "Australian Joint Conference on Artificial Intelligence, AI 2006, 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, Australian Joint Conference on Artificial Intelligence, AI 2006, Hobart, Tasmania, 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.

N1 - Conference code: 19th

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 - https://www.scopus.com/pages/publications/84886432803

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 - Australian Joint Conference on Artificial 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