Local consistency

From Wikipedia, the free encyclopedia

You have new messages (last change).

In constraint satisfaction, local consistency conditions are properties of constraint satisfaction problems related to the consistency of subsets of variables or constraints. Several such conditions exist, the most known being node consistency, arc consistency, and path consistency. Local consistency can be enforced via transformations of the problem called constraint propagation.

Local consistency conditions can be grouped into various classes. The original local consistency conditions require that every consistent assignment can be consistently extended to another variable. Directional consistency only requires this condition to be satisfied when the other variable is higher 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.

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

Contents

[edit] 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, respectively. 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.

[edit] Local consistency

The "standard" local consistency conditions all require that all consistent partial evaluations can be extended to another variable in such a way the resulting assignment is consistent. A partial evaluation is consistent if it satisfies all constraints whose scope is a subset of the assigned variables.

[edit] 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 V with a domain of \left \{ 1, 2, 3, 4 \right \} and a constraint V \le 3, node consistency would restrict the domain to \left \{1, 2, 3 \right \} and the constraint could then be discarded. This pre-processing step simplifies later stages.

[edit] Arc consistency

x2 is arc-consistent with x3 but not with x1, as the value x2=1 does not correspond to any value for x1.
x2 is arc-consistent with x3 but not with x1, as the value x2=1 does not correspond to any value for x1.

A variable of a constraint satisfaction problem is arc-consistent with another one if each of its admissible values is consistent with some admissible value of the second variable. Formally, a variable xi is arc-consistent with another variable xj if, for every value a in the domain of xi there exists a value b in the domain of xj such that (a,b) satisfies the binary constraint between xi and xj. A problem is arc consistent if every variable is arc consistent with any other one.

For example, consider the constraint x < y where the variables range over the domain 1 to 3. Because x can never be 3, there is no arc from 3 to a value in y so it is safe to remove. Likewise, 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.
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 a x1 is arc consistent with x2 but the algorithm reduces the domain of x2, arc consistency of x1 with x2 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 domain change for a whole cycle. The AC-3 algorithm improves over this algorithm by ignoring constraints that have not been modified since they were lastly analyzed. In particular, it works on a set of constraint that initially contains all of them; at each step, it takes a constraint and enforces arc-consistency; if this operation may have produce a violation of arc-consistency over another constraint, it places it back in the set of constraint 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.

[edit] Path consistency

x1 and x2 are not path-consistent with x3. They can be made path consistent by removing the blue values from R12.
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, xi and xj are path consistent with xk if, for every pair of values (a,b) that satisfies the binary constraint between xi and xj, there exists a value c in the domain of xk such that (a,c) and (b,c) satisfy the constraint between xi and xk and between xj and xk, 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.
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.
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 the 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.

[edit] 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 i − 1 variables is i-consistent with another variable if every consistent evaluation of the 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 i-consistency is j-consistency for all 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 exendibility 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.

[edit] Consistency and satisfiability

This instance is arc consistent and contain no empty domain, but has no solution. The blue lines indicate assigments forced by the choice x1=1.
This instance is arc consistent and contain no empty domain, but has no solution. The blue lines indicate assigments 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, x1 = 1 may be consistent with x2 = 1 and with x3 = 1, but these two evaluations are not 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 n consistency establishes satisfiability of problems containing n variables.

[edit] 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.

[edit] 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 \mathop{\rm alldifferent}(x_1,\ldots,x_n) or alldifferent([X1,...,Xn]). This constraint is equivalent to the non-equality of an all pairs of different variables, that is, x_i \not= x_j for every 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.

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 I and vice versa.

[edit] Directional consistency

Directional consistency is the variant of arc, path, and i-consistency tailored for being used by an algorithm that assigns values to variables following a given order of variables. They are similar to their non-directional counterparts, but only require that a consistent assignment to some variables can be consistently extended to another variable that is greater than them according to the order.

[edit] 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.
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 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. the search space of the problem. 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 x_1,\ldots,x_n, a constraint satisfaction problem is directionally arc consistent if every variable xi is arc consistent with any other variable xj such that i < j. Directional path consistency is similar, but two variables xi,xj have to be path consistent with xz only if 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.

[edit] 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 x_1,\ldots,x_n, this algorithm iterates over variables from xn to x1; for variable xj, it enforces arc consistency of every variable of index lower than j with xj.

An instance that is not directional arc consistent: x1=2 does not correspond to any value of x2 and x2=3 does not correspond to any value of x3. No constraint is present between x1 and x3 (corresponding edges are omitted). Enforcing directional arc consistency starts with x3, and makes x2 arc consistent with it by removing the value x2=3. Encorcing directional arc consistent proceed with x2. Since x2=3 has already been removed, both x1=2 and x1=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 xn to x1; for every variable xz two variables xi,xj with i,j < z are considered, and path consistency of them with xz is enforced. No operation is required if the problem contains no constraint on xi and xz or no constraint between xj and xz. However, even if there is no constraint between xi and xj, 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.

[edit] 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 xi or to variable xj, but yet these two extensions are not consistent with each other.

There are two cases in this does not to 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 have 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.

[edit] 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 implicitely indicates the lack of a constraint. This problem has width 2.
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 implicitely indicates the lack of a constraint. This problem has width 2.

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

Every problem can be made strongly directionally 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 xk, the algorithm considers every group of i − 1 variables that have index lower than k and are in a constraint with xk. Consistency of these variables with xk is checked and possibly enforced by removing satisfying assignments from the constraint among all these 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.
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 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 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 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 xi 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 xi. Since this algorithm can be seen as a modification of the previous one with a value i that is changed to the number of parents of each node, it is called adaptive consistency.

This algorithm enforces strongly directional i-consistency with 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 superpolynomally enlarge the instance. As a result, if an instance has induced width bounded by a constant, it can be solved in polynomial time.

[edit] 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 algorightm proceeds from the highest to the lowest variable in turn. At each step, the constraints in the buckets of this variable xi are considered. By definition, these constraints only involve variables that are lower than xi. 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 xi consistently with the constraints in the bucket of xi. This new constraint, if any, is then placed in the appropriate bucket. Since this constraint only involve variables that are lower than xi, it is added to a bucket of a variable that is lower than xi.

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.

[edit] Relational consistency

While the previous definitions of consistency are all about consistency of assignments, relational consistency involves satisfaction of a given constraint or set of constraints only. More precisely, relational consistency implies that every consistent partial assignment can be extended in such a way a given constraint or set of constraints is satisfied. Formally, a constraint C on variables X is relational arc-consistent with one of its variables x if every consistent assignment to X \backslash \{x\} can be extended to x in such a way C is satisfied. The difference between "regular" i consistency and relational arc consistency is that the latter only requires the extended assignment to satisfy a given constraint, while the former requires it to satisfy all relevant constraints.

(Regular) i-consistency: if an evaluation is consistent, it can be extended to another variable in such a way all relevant constraints are satisfied.
(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.
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.

This definition can be extended to more than one constraint and more than one variable. In particular, relational path consistency is similar to relational arc-consistency, but two constraints are used in place of one. Two constraints are relational path consistent with a variable if every consistent assignemt to all their variable but the considered one can be extended in such a way the two constraints are satified.

For more than two constraints, relational m-consistency is defined. Relational m-consistency involves a set of m constraints and a variable that is in the scope of all these constraints. In particular, these m constraints are relational m-consistent with the variabile if every consistent assignment to all other variabiles that are in their scopes can be extended to the variabile in such a way these constraints are satisfied. A problem is m-relational consistent if every set of m constraints is relational m-consistent with every variabile that is in all their scopes. Strong relational m consistency is defined as above: it is the property of being relational k-consistent for every k < m.

Relational consistency can also be defined for more variables, instead of one. A set of m constraints is relational (i,m)-consistent if every consistent assignment to a subset of i of their variables can be extended to an evaluation to all variables that satisfies all constraints. This definition does not exactly extends the above because the variables to which the evaluations are supposed to be extendible are not necessarily in all scopes of the involved constraints.

If an order of the variables is given, relational consistency can be restricted to the cases when the variables(s) the evaluation should be extendable to follow the other variables in the order. This modified condition is called directional relational consistency.

[edit] 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 m-consistent problem when the domains contain at most m elements. In this case, a consistent evaluation of k variables can be always extended to a single other variable. If x_1=a_1,\ldots,x_k=a_k is such an evaluation and xk + 1 is the variable, there are only m possible values the variable can take. If all such values are inconsistent with the evaluation, there are 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 m-or-less constraints, violating the condition of strong relational m-consistency.

The second case is related to a measure of the constraints, rather than the domains. A constraint is 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 m of its values. Problem having m-tight constraints are satisfiable if and only if they are strongly relationally m + 1-consistent.

A row convex matrix: the 1's in each row are contiguous (no 0 in between them).
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 M, where Mij is 0 or 1 depending on whether the i-th value of the domain of xi and the j-th value of the domain of xj 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 xi and xk+1. If a1..ak are values for x1..xk, the rows of a1..ak in each matrix tell the allowed values for xk+1. Row-convex-ness and strong relational path consistency imply the existence of a consistent value ak+1 for xk+1.
Each matrix represents the constraint between xi and xk+1. If a1..ak are values for x1..xk, the rows of a1..ak in each matrix tell the allowed values for xk+1. Row-convex-ness and strong relational path consistency imply the existence of a consistent value ak+1 for xk+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 k variables, the allowed values for the k + 1-th one are given by selecting some rows from some constraints. In particular, for every variable among the k ones, the row relative to its value in the matrix representing the constraint relating it with the 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.

[edit] Uses of local consistency

All forms of local consistency can be enforced by constraint propagation, which may reduce the domains of variables and the sets of assignments satisfying a constraint and may introduce new constraints. Whenever constraint propagation produces an empty domain or an unsatisfiable constraint, the original problem is unsatisfiable. Therefore, all forms of local consistency can be used as approximations of satisfiabilty. More precisely, they can be used as incomplete unsatisfiability algorithms, as they can prove that a problem is unsatisfiable, but are in general unable to prove that a problem is satisfiable. Such approximated algorithms can be used by search algorithms (backtracking, backjumping, local search, etc.) as heuristics for telling whether a partial solution can be extended to satisfy all constraints without further analyzing it.

Even if constraint propagation does not produce an empty domain or an unsatisfiable constraint, it may nevertheless reduce the domains or strengthen the constraints. If this is the case, the search space of the problem is reduced, thus reducing the amount of search needed to solve the problem.

Local consistency proves satisfiability in some restricted cases. This is the case for some special kind of problems and/or for some kinds of local consistency. For example, enforcing arc consistency on binary acyclic problems allows for telling whether the problem is satisfiable. Enforcing strong directional i-consistency allows telling the satisfiability of problems that have induced width i − 1 according to the same order. Adaptive directional consistency allows telling the satisfiability of an arbitrary problem.

[edit] See also

[edit] References

Retrieved from "http://en.wikipedia.org../../../l/o/c/Local_consistency.html"