3.7.12. Arc-consistency

Denotes that, for a given constraint involving only domain variables, there is a filtering algorithm that ensures arc-consistency. A constraint ctr defined on the distinct domain variables V 1 ,β‹―,V n is arc-consistent if and only if for every pair (V,v) such that V is a domain variable of ctr and vβˆˆπ‘‘π‘œπ‘š(V), there exists at least one solution to ctr in which V is assigned the value v. As quoted by C.Β BessiΓ¨re inΒ [Bessiere06], β€œa different name has often been used for arc-consistency on non-binary constraints”, like domain consistency, generalised arc-consistency or hyper arc-consistency.

There is also a weaker form of arc-consistency that also try to remove values from the middle of the domain of a variable V (i.e., unlike bound-consistency which focus on reducing the minimum and maximum value of a variable), called range consistency in Β [Bessiere06], that is defined in the following way. A constraint ctr defined on the distinct domain variables V 1 ,β‹―,V n is range-consistent if and only if, for every pair (V,v) such that V is a domain variable of ctr and vβˆˆπ‘‘π‘œπ‘š(V), there exists at least a solution to ctr in which, (1)Β V is assigned the value v, and (2)Β each variable U∈{V 1 ,β‹―,V n } distinct from V is assigned a value located in its range [U Μ²,U Β―].