Arc Consistency

An important concept in CSPs is the concept of local consistency. Local consistencies are properties that can be applied in a CSP, using (typically) polynomial algorithms, to remove inconsistent values either prior to or during search. Arc consistency is the most commonly used local consistency property in the existing constraint programming engines. We now give a definition of arc consistency.

Definition 2.1   A value $a\in D(x_j)$ is consistent with a constraint $c_{i}$, where $x_j\in vars(c_i)$ if $\exists\tau\in rel(c_i)$ such that $\tau[x_j]=a$ and $\tau$ is valid. In this case we say that $\tau$ is a support of $a$ in $c_i$. A constraint $c_{i}$ is Arc Consistent (AC) iff for each variable $x_j\in vars(c_i)$, $\forall~a\in D(x_j)$, there exists a support for $a$ in $c_i$. A CSP $(X,D,C)$ is arc consistent iff there is no empty domain in $D$ and all the constraints in $C$ are arc consistent.

Arc consistency can be enforced on a CSP by removing all the unsupported values from the domains of variables. By enforcing arc consistency (or some local consistency property $A$ in general) on a CSP $P$, we mean applying an algorithm that yields a new CSP that is arc consistent (or has the property $A$) and has the same set of solutions as $P$. The above definition of arc consistency applies to constraints of any arity. To distinguish between the binary and non-binary cases, we will use the term arc consistency (AC) to refer to the property of arc consistency for binary constraints only. For non-binary constraints we will use the term Generalized Arc Consistency (GAC).

The usefulness of AC processing was recognized early, and as a result, various AC algorithms for binary constraints have been proposed in the literature (e.g. AC-3 in mac77, AC-4 in mh86, AC-5 in vhdt92, AC-7 in bfr95, AC-2001 in br01, AC3.1 in yap01). Some of them have been extended to the non-binary case (e.g. GAC-4 in mm88, GAC-Schema in br97, GAC-2001 in br01). AC can be enforced on a binary CSP with $O(ed^2)$ optimal worst-case time complexity. The worst-case complexity of enforcing GAC on a non-binary CSP is $O(ekd^k)$ [Bessière RéginBessière Régin1996a].

In this paper we use algorithms AC-2001 and GAC-2001 for theoretical and empirical comparisons with specialized algorithms for the encodings. This is not restrictive, in the sense that any generic AC (and GAC) algorithm can be used instead.

Following Debruyne & Bessiére db97, we call a local consistency property $A$ stronger than $B$ iff for any problem enforcing $A$ deletes at least the same values as $B$, and strictly stronger iff it is stronger and there is at least one problem where $A$ deletes more values than $B$. We call $A$ equivalent to $B$ iff they delete the same values for all problems. Similarly, we call a search algorithm $A$ stronger than a search algorithm $B$ iff for every problem $A$ visits at most the same search tree nodes as $B$, and strictly stronger iff it is stronger and there is at least one problem where $A$ visits less nodes than $B$. $A$ is equivalent to $B$ iff they visit the same nodes for all problems.

Following Bacchus et al. bcvbw02, the asymptotic cost (or just cost hereafter) of a search algorithm $A$ is determined by the worst-case number of nodes that the algorithm has to visit to solve the CSP, and the worst-case time complexity of the algorithm at each node¹. As in the paper by Bacchus et al. bcvbw02, we use this measure to set asymptotic bounds in the relative performance of various algorithms. For example, if two algorithms $A$ and $B$ always visit the same nodes and $A$ enforces a property at each node with exponentially higher complexity than the property enforced by $B$, then we say that algorithm $A$ can have an exponentially greater cost than algorithm $B$.