Arc Consistency and Bound Consistency

Two of the most important local consistencies used by constraint solvers: arc consistency (which removes any value that lacks a supporting value in a neighbor's domain) and bound consistency (a cheaper relaxation that only tightens the min and max of each domain). This lesson defines both, shows how to enforce them on a single constraint, and walks through the propagation that occurs when several constraints interact.

Step 1 of 157%

Tutorial

Arc Consistency

A binary constraint $C(X,Y)$ links two variables $X$ and $Y$ with current domains $D(X)$ and $D(Y).$ A value $a \in D(X)$ is said to have support in $D(Y)$ if there exists some $b \in D(Y)$ such that the pair $(a,b)$ satisfies $C.$

The constraint $C(X,Y)$ is arc consistent if:

Every $a \in D(X)$ has a support in $D(Y),$ and
Every $b \in D(Y)$ has a support in $D(X).$

To enforce arc consistency, we remove every value from $D(X)$ and $D(Y)$ that lacks a support.

Illustration. Take $D(X) = \{1, 2, 3\},$ $D(Y) = \{2, 3\},$ and the constraint $X < Y.$

Check $D(X)$ :

\begin{array}{l|l} x=1 & \text{support } y=2 \;\checkmark \\ x=2 & \text{support } y=3 \;\checkmark \\ x=3 & \text{no } y > 3 \;\times \end{array}

Remove $3$ from $D(X).$

Check $D(Y)$ against the updated $D(X) = \{1, 2\}$ :

\begin{array}{l|l} y=2 & x=1 \;\checkmark \\ y=3 & x=1 \;\checkmark \end{array}

No removals. The constraint is now arc consistent: $D(X) = \{1, 2\},$ $D(Y) = \{2, 3\}.$