Local consistency

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.

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.

The constraint satisfaction problems referred to in this article are assumed to be in a special form.

A partial evaluation is consistent if it satisfies all constraints whose scope is a subset of the assigned variables.

Constraint propagation can make the whole problem arc consistent by repeating this removal for all pairs of variables.

Indeed, path consistency can be enforced by removing from a binary constraint all evaluations that cannot be extended to another variable.

While the two definitions are different for a single pair of variables, they are equivalent when referring to the whole problem.

Arc and path consistency can be generalized to non-binary constraints using tuples of variables instead of a single one or a pair.

The particular case of 2-consistency coincides with arc consistency (all problems are assumed node-consistent in this article).

As a result, a solution can be found by iteratively choosing an unassigned variable and recursively propagating across constraints.

Efficient specialized algorithms for enforcing arc consistency on such constraints exist.

The use of the specialized constraint allows for exploiting properties that do not hold for individual binary disequalities.

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.

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.

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 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.

As a result, constraint propagation may produce a problem whose graph has more edges than the original one.

As a result, induced width being 2 is required for strong directional path consistency to guarantee the existence of solutions.

If this is the case, directional strong consistency does not imply satisfiability even if no domain is empty and no constraint is unsatisfiable.

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.

The bucket elimination algorithm proceeds from the highest to the lowest variable in turn.

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.

(non-necessarily unique) constraints that are violated by the evaluation and one of its possible values.

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.

as heuristics for telling whether a partial solution can be extended to satisfy all constraints without further analyzing it.

Adaptive directional consistency allows telling the satisfiability of an arbitrary problem.

is arc consistent with but not with , as the value is not compatible with any value for .
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.
x1 and x2 are not path-consistent with x3. They can be made path consistent by removing the blue values from R12.
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.
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.
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.
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.
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.
(Regular) i-consistency: if an evaluation is consistent, it can be extended to another variable in such a way all relevant constraints are satisfied.
Relational arc consistency: if an evaluation on the variables of a constraint but one is consistent, it can always be extended to that variable in such a way the constraint is satisfied. The cyan edges represent constraints that need not to be satisfied by the extension.
A row convex matrix: the 1's in each row are contiguous (no 0 in between them).
Each matrix represents the constraint between x i and x k +1 . If a 1 ... a k are values for x 1 ... x k , the rows of a 1 ... 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 .