3.7.11. Arc-consistency

Denotes the fact 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, generalized 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 Β―].