Generalised arc consistency

Generalised arc consistency (GAC) is a constraint propagation technique used in CSPs.

First, some definitions:

• Suppose a value $d$ in $\text{dom}(V_i)$ is not consistent wrt a constraint, i.e., there are no assignments to the other variables that satisfy the constraints when $V_i=d$.
• Then, $d$ is said to be arc inconsistent.
• We can remove $d$ from the domain of $V_i$ as this value cannot lead to a solution.
  • This is essentially a more powerful version of forward checking.
• A support for a value assignment $V=d$ in a constraint $C$ is an assignment $A$ to all of the other variables in $\text{scope}(C)$ st $A\cup \{V=d\}$ satisfies $C$.

We say that a constraint $C$ is generalised arc consistent if and only if for every variable $V_i$ in its scope, every value $d_i\in \text{CurDom}(V_i)$ has a support in $C$. Then, we say CSP is GAC iff all of its constraints are GAC.

Pruning

The procedure is a little tricky. If we prune the domain of one variable to make a constraint GAC, we might make a different constraint non-GAC. Thus, we may need to re-achieve GAC for some constraints whenever a domain value is pruned. Thus, GAC is fairly time-intensive.

All constraints must be GAC at every node of the search space. This is accomplished by removing from the domains of the variables all arc inconsistent values. Each time we assign a value to a variable $V$, we check all constraints over $V$ and prune arc inconsistent (i.e., if there’s no support) values from the current domain of the other variables of the constraints.

Since removing a value may trigger inconsistency, we have to repeat the procedure until everything is consistent. We maintain a queue of constraints that need to be made GAC. Constraints are added back to the queue if the domain of one of their variables is changed. The procedure stops when the queue is empty.

When all constraints are GAC, three outcomes are possible:

• Each domain has a single value.
• At least one domain is empty, i.e., it is unsatisfiable.
• Some domains have more than one value. We then need to solve this new CSP, but this is usually a simpler problem to solve.

Analysis

If we have a problem with $n$ variables, $c$ binary constraints, and $d$ max size of a variable domain.

• The maximum number of times we prune the domain of a variable $V$ is $\mathcal{O}(d)$.
• The number of constraints that will be put on the queue when pruning the domain of a variable $V$ is $\mathcal{O}(\text{degree of }v)$.
  • We define the degree of a variable as the number of constraints defined over the variable.
• The sum of degrees of all variables is $2c$.
• So the total number of constraints that will be placed on the queue is $2c\times d\in \mathcal{O}(cd)$.
• And to check the consistency of each constraint, we need $\mathcal{O}(d^2)$.
• So the overall time complexity is $\mathcal{O}(c{d}^3)$.

However, with higher-order constraints, the time complexity is dominated by the number of variables each constraint has to operate over. For $k$ scope of a constraint $C_i$:

• Checking consistency is given by $\mathcal{O}(d^k)$.
• So the overall complexity is $\mathcal{O}(d^{k}T(C))$.
  • Where $T(C)$ is the number of inconsistent values for $C$.