In constraint satisfaction, local consistency conditions are properties of constraint satisfaction problems related to the consistency of subsets of variables or constraints. They can be used to reduce the search space and make the problem easier to solve. Various kinds of local consistency conditions are leveraged, including node consistency, arc consistency, and path consistency.
Every local consistency condition can be enforced by a transformation that changes the problem without changing its solutions; such a transformation is called constraint propagation. Constraint propagation works by reducing domains of variables, strengthening constraints, or creating new constraints. This leads to a reduction of the search space, making the problem easier to solve by some algorithms. Constraint propagation can also be used as an unsatisfiability checker, incomplete in general but complete in some particular cases.
Local consistency conditions can be grouped into various classes. The original local consistency conditions require that every consistent partial assignment (of a particular kind) can be consistently extended to another variable. Directional consistency only requires this condition to be satisfied when the other variable is greater than the ones in the assignment, according to a given order. Relational consistency includes extensions to more than one variable, but this extension is only required to satisfy a given constraint or set of constraints.
Assumptions In this article, a constraint satisfaction problem is defined as a set of variables, a set of domains, and a set of constraints. Variables and domains are associated: the domain of a variable contains all values the variable can take. A constraint is composed of a sequence of variables, called its scope, and a set of their evaluations, which are the evaluations satisfying the constraint.
The constraint satisfaction problems referred to in this article are assumed to be in a special form. A problem is in normalized form, respectively regular form, if every sequence of variables is the scope of at most one constraint or exactly one constraint. The assumption of regularity done only for binary constraints leads to the standardized form. These conditions can always be enforced by combining all constraints over a sequence of variables into a single one and/or adding a constraint that is satisfied by all values of a sequence of variables.
In the figures used in this article, the lack of links between two variables indicate that either no constraint or a constraint satisfied by all values exists between these two variables.
Local consistency The "standard" local consistency conditions all require that all consistent partial evaluations can be extended to another variable in such a way that the resulting assignment is consistent. A partial evaluation is consistent if it satisfies all constraints whose scope is a subset of the assigned variables.
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 with a domain of and a constraint , node consistency would restrict the domain to and the constraint could then be discarded. This pre-processing step simplifies later stages.
Arc consistency
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 is arc consistent with another variable if, for every value in the domain of there exists a value in the domain of such that satisfies the binary constraint between and . A problem is arc consistent if every variable is arc consistent with every other one.
For example, consider the constraint where the variables range over the domain 1 to 3. Because can never be 3, there is no arc from 3 to a value in so it is safe to remove the value 3 from 's domain, resulting in . Likewise, can never be 1, so there is no arc, therefore 1 can be removed from 's domain, resulting in .
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.
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 is arc consistent with but the algorithm reduces the domain of , arc consistency of with 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)
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, and are path consistent with if, for every pair of values that satisfies the binary constraint between and , there exists a value in the domain of such that and satisfy the constraint between and and between and , 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.
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 variables is -consistent with another variable if every consistent evaluation of the 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 -consistency is -consistency for all .
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
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, may be consistent with and with , 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.
enforcing arc consistency establishes satisfiability of problems made of binary constraints with no cycles (a tree of binary constraints); enforcing path consistency establishes satisfiability for binary constraints (possibly with cycles) with binary domains; enforcing strong consistency establishes satisfiability of problems containing 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.