{"history":[],"article":{"id":"7f675695-fe26-4c4a-9f2a-c243eebf4051","title":"Local consistency","slug":"local-consistency","content":":::summary\n:::\n\n# \nIn [constraint satisfaction](https://bliptext.com/articles/constraint-satisfaction), **local [consistency](https://bliptext.com/articles/consistency)** conditions are properties of [constraint satisfaction](https://bliptext.com/articles/constraint-satisfaction) problems related to the [consistency](https://bliptext.com/articles/consistency) of subsets of variables or constraints.\nThey can be used to reduce the search space and make the problem easier to solve.\nVarious kinds of local consistency conditions are leveraged, including **node consistency**, **arc consistency**, and **path consistency**.\nEvery local consistency condition can be enforced by a transformation that changes the problem without changing its solutions; such a transformation is called **constraint propagation**.\nConstraint propagation works by reducing domains of variables, strengthening constraints, or creating new constraints.\nThis leads to a reduction of the search space, making the problem easier to solve by some algorithms.\nConstraint propagation can also be used as an unsatisfiability checker, incomplete in general but complete in some particular cases.\nLocal consistency conditions can be grouped into various classes.\nThe original local consistency conditions require that every consistent partial assignment (of a particular kind) can be consistently extended to another variable.\n**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.\n**Relational consistency** includes extensions to more than one variable, but this extension is only required to satisfy a given constraint or set of constraints.\n\n# Assumptions\nIn this article, a [constraint satisfaction problem](https://bliptext.com/articles/constraint-satisfaction-problem) is defined as a set of variables, a set of domains, and a set of constraints.\nVariables and domains are associated: the domain of a variable contains all values the variable can take.\nA constraint is composed of a sequence of variables, called its scope, and a set of their evaluations, which are the evaluations satisfying the constraint.\nThe constraint satisfaction problems referred to in this article are assumed to be in a special form.\nA 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.\nThe assumption of regularity done only for [binary constraints](https://bliptext.com/articles/binary-constraint) leads to the standardized form.\nThese 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.\nIn 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.\n\n# Local consistency\nThe \"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.\nA partial evaluation is consistent if it satisfies all constraints whose scope is a subset of the assigned variables.\n\n## Node consistency\nNode consistency requires that every unary constraint on a variable is satisfied by all values in the domain of the variable, and vice versa.\nThis condition can be trivially enforced by reducing the domain of each variable to the values that satisfy all unary constraints on that variable.\nAs a result, unary constraints can be neglected and assumed incorporated into the domains.\nFor example, given a variable V with a domain of and a constraint V \\le 3, node consistency would restrict the domain to and the constraint could then be discarded.\nThis pre-processing step simplifies later stages.\n\n## Arc consistency\nA 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.\nFormally, 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.\nA problem is arc consistent if every variable is arc consistent with every other one.\nFor example, consider the constraint x < y where the variables range over the domain 1 to 3.\nBecause x can never be 3, there is no arc from 3 to a value in y so it is safe to remove.\nLikewise, y can never be 1, so there is no arc, therefore it can be removed.\nArc 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.\nThis definition of arc consistency is similar to the above, but is given specific to a constraint.\nThis 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.\nIf a variable is not arc consistent with another one, it can be made so by removing some values from its domain.\nThis 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.\nThis transformation maintains the problem solutions, as the removed values are in no solution anyway.\nConstraint propagation can make the whole problem arc consistent by repeating this removal for all pairs of variables.\nThis process might have to consider a given pair of variables more than once.\nIndeed, removing values from the domain of a variable may cause other variables to become no longer arc consistent with it.\nFor 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.\nA simplistic algorithm would cycle over the pairs of variables, enforcing arc consistency, repeating the cycle until no domains change for a whole cycle.\nThe [AC-3 algorithm](https://bliptext.com/articles/ac-3-algorithm) improves over this algorithm by ignoring constraints that have not been modified since they were last analyzed.\nIn 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.\nThis 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.\n# [x_2 is arc consistent with x_3 but not with x_1, as the value x_2=1 is not compatible with any value for x_1. | upload.wikimedia.org/wikipedia/commons/3/31/Arc-consistency-1.svg]\n# [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. | upload.wikimedia.org/wikipedia/commons/f/f5/Arc-consistency-2.svg]\n\n## Path consistency (k-consistency)\nPath consistency is a property similar to arc consistency, but considers pairs of variables instead of only one.\nA 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.\nFormally, 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.\nThe form of constraint propagation that enforces path consistency works by removing some satisfying assignment from a constraint.\nIndeed, path consistency can be enforced by removing from a binary constraint all evaluations that cannot be extended to another variable.\nAs for arc consistency, this removal might have to consider a binary constraint more than once.\nAs for arc consistency, the resulting problem has the same solutions of the original one, as the removed values are in no solution.\nThe form of constraint propagation that enforces path consistency might introduce new constraints.\nWhen two variables are not related by a binary constraint, they are virtually related by the constraint allowing any pair of values.\nHowever, some pair of values might be removed by constraint propagation.\nThe resulting constraint is no longer satisfied by all pairs of values.\nTherefore, it is no longer a virtual, trivial constraint.\nThe 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.\nWhile the two definitions are different for a single pair of variables, they are equivalent when referring to the whole problem.\n# [x1 and x2 are not path-consistent with x3. They can be made path consistent by removing the blue values from R12. | upload.wikimedia.org/wikipedia/commons/9/9d/Path-consistency-1.svg]\n# [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. | upload.wikimedia.org/wikipedia/commons/6/6f/Path-consistency-2.svg]\n# [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. | upload.wikimedia.org/wikipedia/commons/1/1e/Path-consistency-3.svg]\n\n## Generalizations\nArc and path consistency can be generalized to non-binary constraints using [tuples](https://bliptext.com/articles/tuple) of variables instead of a single one or a pair.\nA 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.\nThis definition extends to whole problems in the obvious way.\nStrong i-consistency is j-consistency for all j \\leq i.\nThe particular case of 2-consistency coincides with arc consistency (all problems are assumed node-consistent in this article).\nOn 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.\nAnother 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.\nNamely, 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.\n\n## Consistency and satisfiability\nConstraint propagation (enforcing a form of local consistency) might produce an empty domain or an [unsatisfiable](https://bliptext.com/articles/unsatisfiable) constraint.\nIn this case, the problem has no solution.\nThe converse is not true in general: an inconsistent instance may be arc consistent or path consistent while having no empty domain or unsatisfiable constraint.\nIndeed, local consistency is only relative to the consistency of groups of variables.\nFor example, arc consistency guarantees that every consistent evaluation of a variable can be consistently extended to another variable.\nHowever, 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.\nFor 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.\nHowever, constraint propagation can be used to prove satisfiability in some cases.\nA set of binary constraints that is arc consistent and has no empty domain can be inconsistent only if the network of constraints contains cycles.\nIndeed, 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.\nAs a result, a solution can be found by iteratively choosing an unassigned variable and recursively propagating across constraints.\nThis 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.\nA similar condition holds for path consistency.\nThe special cases in which satisfiability can be established by enforcing arc consistency and path consistency are the following ones.\n# [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. | upload.wikimedia.org/wikipedia/commons/9/9c/Backtracking-arc-consistency.svg]\n\n## Special cases\nSome definitions or results about relative consistency hold only in special cases.\nWhen the domains are composed of [integers](https://bliptext.com/articles/integer), bound consistency can be defined.\nThis 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.\nWhen constraints are [algebraic](https://bliptext.com/articles/algebraic-functions) or [Boolean](https://bliptext.com/articles/boolean-logic), arc consistency is equivalent to adding new constraint or syntactically modifying an old one, and this can be done by suitably composing constraints.\n\n## Specialized constraints\nSome kinds of constraints are commonly used.\nFor example, the constraint that some variables are all different are often used.\nEfficient specialized algorithms for enforcing arc consistency on such constraints exist.\nThe constraint enforcing a number of variables to be different is usually written or.\nThis constraint is equivalent to the non-equality of all pairs of different variables, that is, 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.\nThe use of the specialized constraint allows for exploiting properties that do not hold for individual binary [disequalities](https://bliptext.com/articles/disequality).\nA first property is that the total number of elements in the domains of all variables must be at least the number of variables.\nMore precisely, after arc consistency is enforced, the number of unassigned variables must not exceed the number of values in the union of their domains.\nOtherwise, the constraint cannot be satisfied.\nThis condition can be checked easily on a constraint in the form, but does not correspond to arc consistency of the network of disequalities.\nA second property of the single constraint is that hyper-arc consistency can be efficiently checked using a [bipartite matching](https://bliptext.com/articles/bipartite-matching) algorithm.\nIn particular, a graph is built with variables and values as the two sets of nodes, and a specialized [bipartite graph](https://bliptext.com/articles/bipartite-graph) matching algorithm is run on it to check the existence of such a matching.\nA different kind of constraint that is commonly used is the one.\nIt was introduced for problems of scheduling and placement.\nAs an example, can be used to formalize the condition in which there are activities, each one with starting time , duration and using an amount of a resource.\nThe constraint states that the total available amount of resources is.\nSpecialized constraint propagation techniques for cumulative constraints exists; different techniques are used depending on which variable domains are already reduced to a single value.\nA third specialized constraint that is used in [constraint logic programming](https://bliptext.com/articles/constraint-logic-programming) is the one.\nIn constraint logic programming, lists are allowed as values of variables.\nA constraint is satisfied if is a list and is the -th element of this list.\nSpecialized constraint propagation rules for these constraints exist.\nAs an example, if and are reduced to a single-value domain, a unique value for can be determined.\nMore generally, impossible values of can be inferred from the domain of I and vice versa.\n\n# Directional consistency\nDirectional 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.\nThey 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.\n\n## Directional arc and path consistency\nIf an algorithm evaluates variables in the order, consistency is only useful when it guarantees that values of lower-index variables are all consistent with values of higher-index ones.\nWhen choosing a value for a variable, values that are inconsistent with all values of an unassigned variable can be neglected.\nIndeed, 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.\nOn 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.\nAssuming that the order of evaluation of the variables is, 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.\nSimilar definitions can be given for the other forms of consistency.\n# [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. | upload.wikimedia.org/wikipedia/commons/f/f6/Directional-arc-1.svg]\n\n## Constraint propagation for arc and path consistency\nConstraint 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.\nIf the order of the variables is, 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.\nDirectional path consistency and strong directional path consistency can be enforced by algorithms similar to the one for arc consistency.\nThey process variables from x_n to x_1; for every variable x_z two variables x_i,x_j with i,j

History