Node consistency

Node consistency requires that every unary constraint on a variable is satisfied by all values in the domain of the variable, and vice versa. This condition can be trivially enforced by reducing the domain of each variable to the values that satisfy all unary constraints on that variable. As a result, unary constraints can be neglected and assumed incorporated into the domains.

For example, given a variable ${\displaystyle V}$ with a domain of ${\displaystyle \left\{1,2,3,4\right\}}$ and a constraint ${\displaystyle V\leq 3}$, node consistency would restrict the domain to ${\displaystyle \left\{1,2,3\right\}}$ and the constraint could then be discarded. This pre-processing step simplifies later stages.

Arc consistency

${\displaystyle x_{2}}$ is arc consistent with ${\displaystyle x_{3}}$ but not with ${\displaystyle x_{1}}$, as the value ${\displaystyle x_{2}=1}$ is not compatible with any value for ${\displaystyle x_{1}}$.

A variable of a constraint satisfaction problem is arc consistent with another one if each of its admissible values are consistent with some admissible value of the second variable. Formally, a variable ${\displaystyle x_{i}}$ is arc consistent with another variable ${\displaystyle x_{j}}$ if, for every value ${\displaystyle a}$ in the domain of ${\displaystyle x_{i}}$ there exists a value ${\displaystyle b}$ in the domain of ${\displaystyle x_{j}}$ such that ${\displaystyle (a,b)}$ satisfies the binary constraint between ${\displaystyle x_{i}}$ and ${\displaystyle x_{j}}$. A problem is arc consistent if every variable is arc consistent with every other one.

For example, consider the constraint ${\displaystyle x<y}$ where the variables range over the domain 1 to 3. Because ${\displaystyle x}$ can never be 3, there is no arc from 3 to a value in ${\displaystyle y}$ so it is safe to remove. Likewise, ${\displaystyle y}$ can never be 1, so there is no arc, therefore it can be removed.

Arc consistency can also be defined relative to a specific binary constraint: a binary constraint is arc consistent if every value of one variable has a value of the second variable such that they satisfy the constraint. This definition of arc consistency is similar to the above, but is given specific to a constraint. This difference is especially relevant for non-normalized problems, where the above definition would consider all constraints between two variables while this one considers only a specific one.

Arc consistency enforced by removing 1 as a value for x2. As a result, x3 is no longer arc consistent with x2 because x3=2 does not correspond to a value for x2.

If a variable is not arc consistent with another one, it can be made so by removing some values from its domain. This is the form of constraint propagation that enforces arc consistency: it removes, from the domain of the variable, every value that does not correspond to a value of the other variable. This transformation maintains the problem solutions, as the removed values are in no solution anyway.

Constraint propagation can make the whole problem arc consistent by repeating this removal for all pairs of variables. This process might have to consider a given pair of variables more than once. Indeed, removing values from the domain of a variable may cause other variables to become no longer arc consistent with it. For example, if ${\displaystyle x_{3}}$ is arc consistent with ${\displaystyle x_{2}}$ but the algorithm reduces the domain of ${\displaystyle x_{2}}$, arc consistency of ${\displaystyle x_{3}}$ with ${\displaystyle x_{2}}$ does not hold any longer, and has to be enforced again.

A simplistic algorithm would cycle over the pairs of variables, enforcing arc consistency, repeating the cycle until no domains change for a whole cycle. The AC-3 algorithm improves over this algorithm by ignoring constraints that have not been modified since they were last analyzed. In particular, it works on a set of constraints that initially contains all constraints; at each step, it takes a constraint and enforces arc consistency; if this operation may have produced a violation of arc consistency over another constraint, it places that constraint back in the set of constraints to analyze. This way, once arc consistency is enforced on a constraint, this constraint is not considered again unless the domain of one of its variables is changed.

Path consistency (k-consistency)

x1 and x2 are not path-consistent with x3. They can be made path consistent by removing the blue values from R12.

Path consistency is a property similar to arc consistency, but considers pairs of variables instead of only one. A pair of variables is path-consistent with a third variable if each consistent evaluation of the pair can be extended to the other variable in such a way that all binary constraints are satisfied. Formally, ${\displaystyle x_{i}}$ and ${\displaystyle x_{j}}$ are path consistent with ${\displaystyle x_{k}}$ if, for every pair of values ${\displaystyle (a,b)}$ that satisfies the binary constraint between ${\displaystyle x_{i}}$ and ${\displaystyle x_{j}}$, there exists a value ${\displaystyle c}$ in the domain of ${\displaystyle x_{k}}$ such that ${\displaystyle (a,c)}$ and ${\displaystyle (b,c)}$ satisfy the constraint between ${\displaystyle x_{i}}$ and ${\displaystyle x_{k}}$ and between ${\displaystyle x_{j}}$ and ${\displaystyle x_{k}}$, respectively.

The form of constraint propagation that enforces path consistency works by removing some satisfying assignment from a constraint. Indeed, path consistency can be enforced by removing from a binary constraint all evaluations that cannot be extended to another variable. As for arc consistency, this removal might have to consider a binary constraint more than once. As for arc consistency, the resulting problem has the same solutions of the original one, as the removed values are in no solution.

Two variables not in a constraint can be considered related by a virtual constraint allowing any possible pair of values, represented by the blue edges in this figure.

Enforcing path consistency of x1 and x2 with x3 removes the edge at the top. The values of x1 and x2 are not longer free, but related by a new actual constraint.

The form of constraint propagation that enforces path consistency might introduce new constraints. When two variables are not related by a binary constraint, they are virtually related by the constraint allowing any pair of values. However, some pair of values might be removed by constraint propagation. The resulting constraint is no longer satisfied by all pairs of values. Therefore, it is no longer a virtual, trivial constraint.

The name "path consistency" derives from the original definition, which involved a pair of variables and a path between them, rather than a pair and a single variable. While the two definitions are different for a single pair of variables, they are equivalent when referring to the whole problem.

Generalizations

Arc and path consistency can be generalized to non-binary constraints using tuples of variables instead of a single one or a pair. A tuple of ${\displaystyle i-1}$ variables is ${\displaystyle i}$-consistent with another variable if every consistent evaluation of the ${\displaystyle i-1}$ variables can be extended with a value of the other variable while preserving consistency. This definition extends to whole problems in the obvious way. Strong ${\displaystyle i}$-consistency is ${\displaystyle j}$-consistency for all ${\displaystyle j\leq i}$.

The particular case of 2-consistency coincides with arc consistency (all problems are assumed node-consistent in this article). On the other hand, 3-consistency coincides with path consistency only if all constraints are binary, because path consistency does not involve ternary constraints while 3-consistency does.

Another way of generalizing arc consistency is hyper-arc consistency or generalized arc consistency, which requires extendibility of a single variable in order to satisfy a constraint. Namely, a variable is hyper-arc consistent with a constraint if every value of the variable can be extended to the other variables of the constraint in such a way the constraint is satisfied.

Consistency and satisfiability

This instance is arc consistent and contains no empty domain, but has no solution. The blue lines indicate assignments forced by the choice x1=1.

Constraint propagation (enforcing a form of local consistency) might produce an empty domain or an unsatisfiable constraint. In this case, the problem has no solution. The converse is not true in general: an inconsistent instance may be arc consistent or path consistent while having no empty domain or unsatisfiable constraint.

Indeed, local consistency is only relative to the consistency of groups of variables. For example, arc consistency guarantees that every consistent evaluation of a variable can be consistently extended to another variable. However, when a single value of a variable is extended to two other variables, there is no guarantee that these two values are consistent with each other. For example, ${\displaystyle x_{1}=1}$ may be consistent with ${\displaystyle x_{2}=1}$ and with ${\displaystyle x_{3}=1}$, but these two evaluations may not be consistent with each other.

However, constraint propagation can be used to prove satisfiability in some cases. A set of binary constraints that is arc consistent and has no empty domain can be inconsistent only if the network of constraints contains cycles. Indeed, if the constraints are binary and form an acyclic graph, values can always be propagated across constraints: for every value of a variable, all variables in a constraint with it have a value satisfying that constraint. As a result, a solution can be found by iteratively choosing an unassigned variable and recursively propagating across constraints. This algorithm never tries to assign a value to a variable that is already assigned, as that would imply the existence of cycles in the network of constraints.

A similar condition holds for path consistency. The special cases in which satisfiability can be established by enforcing arc consistency and path consistency are the following ones.

1. enforcing arc consistency establishes satisfiability of problems made of binary constraints with no cycles (a tree of binary constraints);
2. enforcing path consistency establishes satisfiability for binary constraints (possibly with cycles) with binary domains;
3. enforcing strong ${\displaystyle n}$ consistency establishes satisfiability of problems containing ${\displaystyle n}$ variables.

Special cases

Some definitions or results about relative consistency hold only in special cases.

When the domains are composed of integers, bound consistency can be defined. This form of consistency is based on the consistency of the extreme values of the domains, that is, the minimum and maximum values a variable can take.

When constraints are algebraic or Boolean, arc consistency is equivalent to adding new constraint or syntactically modifying an old one, and this can be done by suitably composing constraints.

Specialized constraints

Some kinds of constraints are commonly used. For example, the constraint that some variables are all different are often used. Efficient specialized algorithms for enforcing arc consistency on such constraints exist.

The constraint enforcing a number of variables to be different is usually written ${\displaystyle \mathop {\rm {alldifferent}} (x_{1},\ldots ,x_{n})}$ or alldifferent([X1,...,Xn]). This constraint is equivalent to the non-equality of all pairs of different variables, that is, ${\displaystyle x_{i}\not =x_{j}}$ for every ${\displaystyle i\not =j}$. When the domain of a variable is reduced to a single value, this value can be removed from all other domains by constraint propagation when enforcing arc consistency. The use of the specialized constraint allows for exploiting properties that do not hold for individual binary disequalities.

A first property is that the total number of elements in the domains of all variables must be at least the number of variables. More precisely, after arc consistency is enforced, the number of unassigned variables must not exceed the number of values in the union of their domains. Otherwise, the constraint cannot be satisfied. This condition can be checked easily on a constraint in the alldifferent form, but does not correspond to arc consistency of the network of disequalities. A second property of the single alldifferent constraint is that hyper-arc consistency can be efficiently checked using a bipartite matching algorithm. In particular, a graph is built with variables and values as the two sets of nodes, and a specialized bipartite graph matching algorithm is run on it to check the existence of such a matching.^[1]

A different kind of constraint that is commonly used is the cumulative one. It was introduced for problems of scheduling and placement. As an example, cumulative([S1,...,Sm], [D1,...,Dm], [R1,...,Rm], L) can be used to formalize the condition in which there are m activities, each one with starting time si, duration di and using an amount ri of a resource. The constraint states that the total available amount of resources is L. Specialized constraint propagation techniques for cumulative constraints exists; different techniques are used depending on which variable domains are already reduced to a single value.

A third specialized constraint that is used in constraint logic programming is the element one. In constraint logic programming, lists are allowed as values of variables. A constraint element(I, L, X) is satisfied if L is a list and X is the I-th element of this list. Specialized constraint propagation rules for these constraints exist. As an example, if L and I are reduced to a single-value domain, a unique value for X can be determined. More generally, impossible values of X can be inferred from the domain of ${\displaystyle I}$ and vice versa.

Directional arc and path consistency

An instance that is directionally arc consistent according to the order x1 x2 x3 but not arc consistent (no constraint is present between x1 and x3; corresponding edges omitted). Every value of a lower-index variable corresponds to values of higher index variables. Question marks indicate points where the converse does not hold.

If an algorithm evaluates variables in the order ${\displaystyle x_{1},\ldots ,x_{n}}$, consistency is only useful when it guarantees that values of lower-index variables are all consistent with values of higher-index ones.

When choosing a value for a variable, values that are inconsistent with all values of an unassigned variable can be neglected. Indeed, even if these values are all consistent with the current partial evaluation, the algorithm will later fail to find a consistent value for the unassigned variable. On the other hand, enforcing consistency with variables that are already evaluated is not necessary: if the algorithm chooses a value that is inconsistent with the current partial evaluation, inconsistency is detected anyway.

Assuming that the order of evaluation of the variables is ${\displaystyle x_{1},\ldots ,x_{n}}$, a constraint satisfaction problem is directionally arc consistent if every variable ${\displaystyle x_{i}}$ is arc consistent with any other variable ${\displaystyle x_{j}}$ such that ${\displaystyle i<j}$. Directional path consistency is similar, but two variables ${\displaystyle x_{i},x_{j}}$ have to be path consistent with ${\displaystyle x_{z}}$ only if ${\displaystyle i,j<z}$. Strong directional path consistency means both directional path consistency and directional arc consistency. Similar definitions can be given for the other forms of consistency.

Constraint propagation for arc and path consistency

Constraint propagation enforcing directional arc consistency iterates over variables from the last to the first, enforcing at each step the arc consistency of every variable of lower index with it. If the order of the variables is ${\displaystyle x_{1},\ldots ,x_{n}}$, this algorithm iterates over variables from ${\displaystyle x_{n}}$ to ${\displaystyle x_{1}}$; for variable ${\displaystyle x_{j}}$, it enforces arc consistency of every variable of index lower than ${\displaystyle j}$ with ${\displaystyle x_{j}}$.

An instance that is not directional arc consistent: ${\displaystyle x_{1}=2}$ does not correspond to any value of ${\displaystyle x_{2}}$ and ${\displaystyle x_{2}=3}$ does not correspond to any value of ${\displaystyle x_{3}}$. No constraint is present between ${\displaystyle x_{1}}$ and ${\displaystyle x_{3}}$ (corresponding edges are omitted).	Enforcing directional arc consistency starts with ${\displaystyle x_{3}}$, and makes ${\displaystyle x_{2}}$ arc consistent with it by removing the value ${\displaystyle x_{2}=3}$.	Enforcing directional arc consistency proceeds with ${\displaystyle x_{2}}$. Since ${\displaystyle x_{2}=3}$ has already been removed, both ${\displaystyle x_{1}=2}$ and ${\displaystyle x_{1}=3}$ are removed.

Directional path consistency and strong directional path consistency can be enforced by algorithms similar to the one for arc consistency. They process variables from ${\displaystyle x_{n}}$ to ${\displaystyle x_{1}}$; for every variable ${\displaystyle x_{z}}$ two variables ${\displaystyle x_{i},x_{j}}$ with ${\displaystyle i,j<z}$ are considered, and path consistency of them with ${\displaystyle x_{z}}$ is enforced. No operation is required if the problem contains no constraint on ${\displaystyle x_{i}}$ and ${\displaystyle x_{z}}$ or no constraint between ${\displaystyle x_{j}}$ and ${\displaystyle x_{z}}$. However, even if there is no constraint between ${\displaystyle x_{i}}$ and ${\displaystyle x_{j}}$, a trivial one is assumed. If constraint propagation reduces its set of satisfying assignments, it effectively create a new non-trivial constraint. Constraint propagation enforcing strong directional path consistency is similar, but also enforces arc consistency.

Directional consistency and satisfiability

Directional consistency guarantees that partial solutions satisfying a constraint can be consistently extended to another variable of higher index. However, it does not guarantee that the extensions to different variables are consistent with each other. For example, a partial solution may be consistently extended to variable ${\displaystyle x_{i}}$ or to variable ${\displaystyle x_{j}}$, but yet these two extensions are not consistent with each other.

There are two cases in which this does not happen, and directional consistency guarantees satisfiability if no domain is empty and no constraint is unsatisfiable.

The first case is that of a binary constraint problem with an ordering of the variables that makes the ordered graph of constraint having width 1. Such an ordering exists if and only if the graph of constraints is a tree. If this is the case, the width of the graph bounds the maximal number of lower (according to the ordering) nodes a node is joined to. Directional arc consistency guarantees that every consistent assignment to a variable can be extended to higher nodes, and width 1 guarantees that a node is not joined to more than one lower node. As a result, once the lower variable is assigned, its value can be consistently extended to every higher variable it is joined with. This extension cannot later lead to inconsistency. Indeed, no other lower variable is joined to that higher variable, as the graph has width 1.

As a result, if a constraint problem has width 1 with respect to an ordering of its variables (which implies that its corresponding graph is a tree) and the problem is directionally arc consistent with respect to the same ordering, a solution (if any) can be found by iteratively assigning variables according to the ordering.

The second case in which directional consistency guarantees satisfiability if no domain is empty and no constraint is unsatisfiable is that of binary constraint problems whose graph has induced width 2, using strong directional path consistency. Indeed, this form of consistency guarantees that every assignment to a variable or a pair of variables can be extended to a higher variable, and width 2 guarantees that this variable is not joined to another pair of lower variables.

The reason why the induced width is considered instead of the width is that enforcing directional path consistency may add constraints. Indeed, if two variables are not in the same constraint but are in a constraint with a higher variable, some pairs of their values may violate path consistency. Removing such pairs creates a new constraint. As a result, constraint propagation may produce a problem whose graph has more edges than the original one. However, all these edges are necessarily in the induced graph, as they are all between two parents of the same node. Width 2 guarantees that every consistent partial evaluation can be extended to a solution, but this width is relative to the generated graph. As a result, induced width being 2 is required for strong directional path consistency to guarantee the existence of solutions.

Directional i-consistency

The blue lines indicate that there is no constraint between x3 and x4, so that every pair of values is allowed. In these images, the lack of edges between two variables implicitly indicates the lack of a constraint. This problem has width 2.

Directional ${\displaystyle i}$-consistency is the guarantee that every consistent assignment to ${\displaystyle i-1}$ variables can be consistently extended to another variable that is higher in the order. Strong directional ${\displaystyle i}$-consistency is defined in a similar way, but all groups of at most ${\displaystyle i-1}$ variables are considered. If a problem is strongly directionally ${\displaystyle i}$-consistent and has width less than ${\displaystyle i}$ and has no empty domain or unsatisfiable constraint, it has solutions.

Every problem can be made strongly directionally ${\displaystyle i}$-consistent, but this operation may increase the width of its corresponding graphs. The constraint propagation procedure that enforces directional consistency is similar to that used for directional arc consistency and path consistency. The variables are considered in turn, from the last to the first according to the order. For variable ${\displaystyle x_{k}}$, the algorithm considers every group of ${\displaystyle i-1}$ variables that have index lower than ${\displaystyle k}$ and are in a constraint with ${\displaystyle x_{k}}$. Consistency of these variables with ${\displaystyle x_{k}}$ is checked and possibly enforced by removing satisfying assignments from the constraint among all these ${\displaystyle i}$ variables (if any, or creating a new one otherwise).

Enforcing consistency on x5 removes the red line, thus creating a new non-trivial constraint between x3 and x4. As a result, x4 has x3 as a new parent, in addition to x1 and x2. This change increases the width to 3.

This procedure generates a strongly directional ${\displaystyle i}$-consistent instance. However, it may also add new constraints to the instance. As a result, even if the width of the original problem is ${\displaystyle i}$, the width of the resulting instance may be greater. If this is the case, directional strong consistency does not imply satisfiability even if no domain is empty and no constraint is unsatisfiable.

However, constraint propagation only adds constraints to variables that are lower than the one it is currently considering. As a result, no constraint over a variable is modified or added once the algorithm has dealt with this variable. Instead of considering a fixed ${\displaystyle i}$, one can modify it to the number of parents of each considered variable (the parents of a variable are the variables of index lower than the variable and that are in a constraint with the variable). This corresponds to considering all parents of a given variables at each step. In other words, for each variable ${\displaystyle x_{i}}$ from the last to the first, all its parents are included in a new constraint that limits their values to the ones that are consistent with ${\displaystyle x_{i}}$. Since this algorithm can be seen as a modification of the previous one with a value ${\displaystyle i}$ that is changed to the number of parents of each node, it is called adaptive consistency.

This algorithm enforces strongly directional ${\displaystyle i}$-consistency with ${\displaystyle i}$ equal to the induced width of the problem. The resulting instance is satisfiable if and only if no domain or constraint is made empty. If this is the case, a solution can be easily found by iteratively setting an unassigned variable to an arbitrary value, and propagating this partial evaluation to other variables. This algorithm is not always polynomial-time, as the number of constraints introduced by enforcing strong directional consistency may produce an exponential increase of size. The problem is however solvable in polynomial time if the enforcing strong directional consistency does not superpolynomially enlarge the instance. As a result, if an instance has induced width bounded by a constant, it can be solved in polynomial time.

Bucket elimination

Bucket elimination is a satisfiability algorithm. It can be defined as a reformulation of adaptive consistency. Its definitions uses buckets, which are containers for constraint, each variable having an associated bucket. A constraint always belongs to the bucket of its highest variable.

The bucket elimination algorithm proceeds from the highest to the lowest variable in turn. At each step, the constraints in the buckets of this variable ${\displaystyle x_{i}}$ are considered. By definition, these constraints only involve variables that are lower than ${\displaystyle x_{i}}$. The algorithm modifies the constraint between these lower variables (if any, otherwise it creates a new one). In particular, it enforces their values to be extendible to ${\displaystyle x_{i}}$ consistently with the constraints in the bucket of ${\displaystyle x_{i}}$. This new constraint, if any, is then placed in the appropriate bucket. Since this constraint only involves variables that are lower than ${\displaystyle x_{i}}$, it is added to a bucket of a variable that is lower than ${\displaystyle x_{i}}$.

This algorithm is equivalent to enforcing adaptive consistency. Since they both enforce consistency of a variable with all its parents, and since no new constraint is added after a variable is considered, what results is an instance that can be solved without backtracking.

Since the graph of the instance they produce is a subgraph of the induced graph, if the induced width is bounded by a constant the generated instance is of size polynomial in the size of the original instance. As a result, if the induced width of an instance is bounded by a constant, solving it can be done in polynomial time by the two algorithms.

Relational consistency and satisfiability

A constraint satisfaction problem may be relationally consistent, have no empty domain or unsatisfiable constraint, and yet be unsatisfiable. There are however some cases in which this is not possible.

The first case is that of strongly relational ${\displaystyle m}$-consistent problem when the domains contain at most ${\displaystyle m}$ elements. In this case, a consistent evaluation of ${\displaystyle k}$ variables can be always extended to a single other variable. If ${\displaystyle x_{1}=a_{1},\ldots ,x_{k}=a_{k}}$ is such an evaluation and ${\displaystyle x_{k+1}}$ is the variable, there are only ${\displaystyle m}$ possible values the variable can take. If all such values are inconsistent with the evaluation, there are ${\displaystyle m}$ (non-necessarily unique) constraints that are violated by the evaluation and one of its possible values. As a result, the evaluation cannot be extended to satisfy all these ${\displaystyle m}$-or-less constraints, violating the condition of strong relational ${\displaystyle m}$-consistency.

The second case is related to a measure of the constraints, rather than the domains. A constraint is ${\displaystyle m}$-tight if every evaluation to all its variables but one can be extended to satisfy the constraint either by all possible values of the other variable or by at most ${\displaystyle m}$ of its values. Problem having ${\displaystyle m}$-tight constraints are satisfiable if and only if they are strongly relationally ${\displaystyle m+1}$-consistent.

A row convex matrix: the 1's in each row are contiguous (no 0 in between them).

The third case is that of binary constraints that can be represented by row-convex matrices. A binary constraint can be represented by a bidimensional matrix ${\displaystyle M}$, where ${\displaystyle M_{ij}}$ is 0 or 1 depending on whether the ${\displaystyle i}$-th value of the domain of ${\displaystyle x_{i}}$ and the ${\displaystyle j}$-th value of the domain of ${\displaystyle x_{j}}$ satisfy the constraint. A row of this matrix is convex if the 1's it contains are consecutive (formally, if two elements are 1, all elements in between are 1 as well). A matrix is row convex if all its rows are convex.

Each matrix represents the constraint between x_i and x_k+1. If a₁...a_k are values for x₁...x_k, the rows of a₁...a_k in each matrix tell the allowed values for x_k+1. Row-convex-ness and strong relational path consistency imply the existence of a consistent value a_k+1 for x_k+1.

The condition that makes strong relational path consistency equivalent to satisfiability is that of constraint satisfaction problems for which there exists an order of the variables that makes all constraint to be represented by row convex matrices. This result is based on the fact that a set of convex rows having a common element pairwise also have a globally common element. Considering an evaluation over ${\displaystyle k}$ variables, the allowed values for the ${\displaystyle k+1}$-th one are given by selecting some rows from some constraints. In particular, for every variable among the ${\displaystyle k}$ ones, the row relative to its value in the matrix representing the constraint relating it with the ${\displaystyle k+1}$ one represents the allowed values of the latter. Since these row are convex, and they have a common element pairwise because of path consistency, they also have a shared common element, which represents a value of the last variable that is consistent with the other ones.