Bucket Elimination

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

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.

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 $V$ with a domain of $\left \$ and a constraint $V \le 3$, node consistency would restrict the domain to $\left \$ 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 $x_i$ is arc-consistent with another variable $x_j$ if, for every value $a$ in the domain of $x_i$ there exists a value $b$ in the domain of $x_j$ such that $(a,b)$ satisfies the binary constraint between $x_i$ and $x_j$. A problem is arc consistent if every variable is arc consistent with every 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.

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 $x_3$ is arc consistent with $x_2$ but the algorithm reduces the domain of $x_2$, arc consistency of $x_3$ with $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 of them; 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 it 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

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, $x_i$ and $x_j$ are path consistent with $x_k$ if, for every pair of values $(a,b)$ that satisfies the binary constraint between $x_i$ and $x_j$, there exists a value $c$ in the domain of $x_k$ such that $(a,c)$ and $(b,c)$ satisfy the constraint between $x_i$ and $x_k$ and between $x_j$ and $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.

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 $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 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, $x_1=1$ may be consistent with $x_2=1$ and with $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.

# 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 $n$ consistency establishes satisfiability of problems containing $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 $\mathop(x_1,\ldots,x_n)$ or alldifferent( 1,...,Xn. This constraint is equivalent to the non-equality of 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( 1,...,Sm 1,...,Dm 1,...,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.

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.

Directional arc and path consistency

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. 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 $x_i$ is arc consistent with any other variable $x_j$ such that $i < j$. Directional path consistency is similar, but two variables $x_i, x_j$ have to be path consistent with $x_z$ 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.

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 $x_n$ to $x_1$; for variable $x_j$, it enforces arc consistency of every variable of index lower than $j$ with $x_j$.

Directional path consistency and strong directional path consistency can be enforced by algorithms similar to the one for arc consistency. They process variables from $x_n$ to $x_1$; for every variable $x_z$ two variables $x_i,x_j$ with i,j are considered, and path consistency of them with $x_z$ is enforced. No operation is required if the problem contains no constraint on $x_i$ and $x_z$ or no constraint between $x_j$ and $x_z$. However, even if there is no constraint between $x_i$ and $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 $x_i$ or to variable $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

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 $x_k$, the algorithm considers every group of $i-1$ variables that have index lower than $k$ and are in a constraint with $x_k$. Consistency of these variables with $x_k$ 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).

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 $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 $x_i$. 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 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 $x_i$ are considered. By definition, these constraints only involve variables that are lower than $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 $x_i$ consistently with the constraints in the bucket of $x_i$. This new constraint, if any, is then placed in the appropriate bucket. Since this constraint only involves variables that are lower than $x_i$, it is added to a bucket of a variable that is lower than $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

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 that 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 \$ 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.

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 assignment to all their variables but the considered one can be extended in such a way the two constraints are satisfied.

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 variable if every consistent assignment to all other variables that are in their scopes can be extended to the variable 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 variable 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.

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.

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

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 $M_$ is 0 or 1 depending on whether the $i$-th value of the domain of $x_i$ and the $j$-th value of the domain of $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.

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.

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 satisfiability. 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 (see Complexity of constraint satisfaction#Restrictions). 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.

See also

*Unit propagation
*Constraint programming
*Constraint logic programming
*Look-ahead (backtracking)

External links

Constraint Propagation
- Dissertation by Guido Tack giving a good survey of theory and implementation issues

References

*
*
*
* {{ISBN, 0-262-13341-5

Constraint programming