Local consistency
Local consistency refers to a class of properties in constraint satisfaction problems (CSPs) that ensure partial assignments to small subsets of variables—typically of size 1 to 3—can be extended to consistent assignments involving additional variables, allowing for the systematic elimination of inconsistent values from variable domains to simplify problem solving.[1] These properties, enforced via polynomial-time algorithms, serve as preprocessing steps or integrated mechanisms in search-based solvers to reduce the computational complexity of finding solutions in CSPs, which model combinatorial optimization and decision problems across fields like artificial intelligence, scheduling, and configuration.[2] Key levels of local consistency form a hierarchy of increasing strength. Node consistency, the simplest form, requires that every value in a variable's domain satisfies all unary constraints involving that variable alone.[1] Arc consistency extends this to binary constraints, mandating that for every constraint between two variables x and y, each value in x's domain has at least one supporting value in y's domain that satisfies the constraint, and vice versa; this can be achieved in O(ed^2) time for a CSP with e constraints and domain size d.[2] Path consistency further generalizes to triples of variables, ensuring that constraints between any two are compatible through the third via relational composition.[1] Higher-order k-consistency requires that every consistent assignment to any k-1 variables can be extended to a consistent assignment including one more variable, providing stronger guarantees but at higher computational cost, often exponential in k.[1] The application of local consistency plays a central role in CSP resolution by preserving all solutions while pruning the search space, often dramatically improving efficiency in backtracking algorithms like AC-3 for arc consistency.[2] Extensions, such as generalized arc consistency for constraints of arity greater than two, address non-binary relations with complexities like O(ekd^k), where k is the arity.[2] In advanced frameworks like junction graphs for constraint-based inference, local consistency concepts like single cluster consistency ensure local tightness in graphical models, enabling scalable inference via message-passing protocols.[3] While full global consistency (solvability) may require higher levels, local methods provide practical approximations that detect early failures and unify techniques across related domains, including relational databases and theorem proving.[4]Introduction
Definition and Assumptions
In constraint satisfaction problems (CSPs), the standard formulation involves a finite set of variables X = \{x_1, \dots, x_n\}, where each variable x_i is associated with a finite domain D(x_i) of possible values, and a finite set of constraints C, each defined as a relation over a subset of variables specifying the allowable value combinations for those variables.[5][6] Local consistency refers to a property of partial assignments in a CSP, where an assignment to a subset of variables Y \subseteq X is locally consistent if it assigns values from the respective domains and satisfies all constraints whose scopes are contained within Y.[5] More precisely, it ensures that solutions to local subproblems—defined over small subsets of variables and the constraints among them—are solvable and, in certain forms, extensible to larger subsets without violating additional constraints.[7] This concept encompasses various levels, such as node consistency as the simplest form where each variable individually satisfies its unary constraints.[6] Key assumptions underlying local consistency include finite domains for all variables, which ensures tractability in enumeration and pruning; constraints of binary or higher arity, allowing representation as relations over two or more variables; and, unless otherwise specified, undirected constraint graphs where edges represent symmetric binary constraints between variables.[5][7] These assumptions facilitate the modeling of CSPs as networks where local checks can be efficiently propagated. Local consistency emphasizes subproblems over complete global solutions because directly solving the full CSP is often NP-complete, whereas verifying and enforcing consistency on small subsets prunes inconsistent values early, significantly reducing the search space for backtracking algorithms without guaranteeing a global solution.[6][7]Importance in Constraint Satisfaction
Local consistency plays a pivotal role in solving constraint satisfaction problems (CSPs) by enabling the early detection and elimination of inconsistent variable assignments, which significantly reduces the search space explored during backtracking algorithms. In CSP solvers, enforcing local consistency prunes domains of variables by removing values that cannot participate in any complete solution, thereby minimizing the frequency and depth of backtracking failures that occur when incompatible assignments are discovered late in the search process. This pruning effect is particularly valuable in combinatorial problems where exhaustive search would otherwise be computationally prohibitive, as it transforms a potentially exponential search tree into a more manageable one. One key benefit of local consistency is its ability to identify unsatisfiable CSPs without resorting to a full search; for instance, if enforcing a certain level of consistency results in an empty domain for any variable, the problem is provably inconsistent, avoiding unnecessary exploration. Additionally, local consistency provides an approximation to global consistency, where lower levels like arc consistency offer a tractable way to ensure that partial assignments are extendable to larger subsets of variables, while higher levels strengthen this guarantee at the cost of increased computation. For certain levels, such as arc and path consistency, enforcement can be achieved in polynomial time relative to the problem size, making it feasible for preprocessing steps in solvers.[8][9] The origins of local consistency trace back to the 1970s, emerging from early CSP applications in computer vision, notably Waltz's 1975 line-labeling algorithm, which propagated constraints across line junctions in drawings to resolve labeling ambiguities efficiently without exhaustive enumeration. This approach was formalized and generalized in Montanari's 1974 work on networks of constraints for picture processing, introducing relational representations and consistency properties, and further developed by Mackworth in 1977, who defined a hierarchy of consistency levels to systematically reduce local inconsistencies in relational networks. However, trade-offs exist: while higher-order consistencies (e.g., path or k-consistency) provide stronger pruning and better approximation of global solutions, they incur substantially higher computational costs, often scaling cubically or worse with the number of variables and domain sizes, necessitating careful selection based on problem characteristics.[9][6]Basic Local Consistencies
Node Consistency
Node consistency represents the simplest form of local consistency in constraint satisfaction problems (CSPs), addressing only unary constraints on individual variables. In a CSP, a variable x_i is node-consistent if every value in its domain D(x_i) satisfies all unary constraints applicable to x_i. This ensures that no value is inherently infeasible due to constraints involving only that single variable, thereby pruning the search space at the outset without considering interactions between variables.[10][11] Formally, for every unary constraint C(x_i), the domain D(x_i) is node-consistent if \forall a \in D(x_i), (x_i = a) \in C(x_i). This condition guarantees that each potential assignment to x_i alone is valid under its unary restrictions. Enforcing node consistency across all variables in the CSP results in a network that is fully node-consistent, eliminating trivial inconsistencies before more complex checks.[10][12] The algorithm for achieving node consistency is straightforward and efficient: for each variable x_i, iterate through its domain and remove any value a that violates a unary constraint C(x_i). This process operates in O(|D| \cdot k) time, where |D| is the domain size and k is the number of unary constraints on x_i, making it computationally inexpensive even for large domains. As a prerequisite for higher consistencies like arc consistency, node consistency establishes a clean foundation by resolving unary issues independently.[11][13] A practical example arises in scheduling CSPs, where a unary constraint might require a task to occupy a time slot of at least a certain duration. Node consistency ensures that only valid time slots—those accommodating the task's duration—are retained in the domain for that variable, filtering out incompatible options like overly short intervals. This step simplifies subsequent solving without altering the problem's core structure.[10]Arc Consistency
Arc consistency is a local consistency property in constraint satisfaction problems (CSPs) that ensures, for every pair of variables connected by a binary constraint, that each value in the domain of one variable has at least one compatible value in the domain of the other variable.[6] This property focuses on pairwise interactions, pruning inconsistent values from domains to reduce the search space without losing solutions.[6] Formally, in a CSP defined by variables X = \{x_1, \dots, x_n\}, domains D(x_i), and binary constraints C(x_i, x_j), an arc (x_i, x_j) is arc-consistent if for every value a \in D(x_i), there exists a value b \in D(x_j) such that (a, b) \in C(x_i, x_j).[6] The reverse arc (x_j, x_i) must satisfy the symmetric condition. A CSP is arc-consistent if all its arcs are arc-consistent.[6] Enforcing arc consistency involves revising domains through constraint propagation, which removes values lacking support from neighboring variables. This builds on node consistency by extending filtering from unary constraints to binary ones. Key algorithms for achieving arc consistency include AC-3 and AC-4. AC-3, introduced by Mackworth, uses a queue to process arcs whose domains may have changed, repeatedly revising domains until no further reductions occur or a domain empties (indicating inconsistency).[6] Its time complexity is O(e d^3), where e is the number of arcs and d is the maximum domain size, as each arc may be revised up to O(d^2) times with O(d) work per revision.[6] AC-4 improves on AC-3 by using support counting and directional processing to avoid redundant revisions, achieving optimal worst-case time complexity of O(e d^2). In AC-4, supports for each value are precomputed and updated incrementally, counting compatible pairs to identify unsupported values efficiently. This makes AC-4 particularly effective for dense constraint graphs, though AC-3 often performs better in practice for sparse networks due to lower overhead.[14] A classic example is the map coloring problem, where regions are variables, colors are domain values, and adjacent regions share "not equal" constraints. Arc consistency ensures that for each color assigned to a region, at least one different color remains available for each adjacent region, pruning impossible colorings early.[6]Higher-Order Local Consistencies
Path Consistency
Path consistency extends arc consistency by ensuring that consistent assignments to pairs of variables can be extended to a third variable connected via a path of length two in the constraint graph. Introduced by Montanari in 1974, it addresses potential inconsistencies that arc consistency alone might overlook in chains of constraints.[15] Formally, in a constraint satisfaction problem (CSP) defined by variables X = \{x_i\}, domains D(x_i), and binary constraints C(x_i, x_j), a path (x_i, x_j, x_k) is path-consistent if for every pair of values a \in D(x_i) and b \in D(x_j) such that (a, b) \in C(x_i, x_j), there exists a value c \in D(x_k) satisfying (b, c) \in C(x_j, x_k). If a direct binary constraint C(x_i, x_k) exists, then additionally (a, c) \in C(x_i, x_k) must hold. A CSP is path-consistent if every such path of length two is path-consistent; Montanari proved that checking all length-two paths suffices for the entire network due to transitivity properties.[15] Enforcing path consistency typically involves algorithms like PC-1 and PC-2. PC-1, proposed by Montanari, iterates over all triples of variables, revising the constraints by removing unsupported value combinations until no changes occur; this brute-force approach has time complexity O(n^3 d^3), where n is the number of variables and d is the maximum domain size.[15] PC-2, developed by Mackworth in 1977, improves efficiency by using a queue to process only potentially inconsistent paths, analogous to the AC-3 algorithm for arc consistency, achieving worst-case time complexity O(n^3 d^3) but often performing better in practice.[6] Despite its strengths, path consistency does not guarantee global consistency or solvability of the CSP, particularly in dense constraint graphs where higher-order interactions may introduce inconsistencies undetectable by ternary checks. For instance, certain four-variable networks can be path-consistent yet lack a complete solution, highlighting the need for stronger consistencies in complex problems.[6]k-Consistency
k-Consistency generalizes local consistency in constraint satisfaction problems (CSPs) by ensuring extendability of partial assignments to larger tuples of variables. A CSP is k-consistent if every partial assignment to any k variables that satisfies all constraints among them can be extended to an assignment of k+1 variables that satisfies all relevant constraints.[16] Formally, for any set of k+1 variables and any consistent assignment to a subset of k variables from that set, there exists a value in the domain of the remaining variable such that the full assignment to the k+1 variables is consistent with all constraints involving them.[16] This property builds on lower-order consistencies, with path consistency corresponding to 3-consistency as a special case. Achieving n-consistency, where n is the total number of variables, equates to full global consistency and guarantees a solution if one exists.[16] The computational cost of establishing k-consistency grows rapidly with k, with a time complexity of O(n^k d^k), where n is the number of variables and d is the maximum domain size; this renders it feasible only for small values of k in practice, typically up to 3 or 4.[17] An illustrative example arises in puzzle solving, such as Sudoku, where enforcing 3-consistency on variables within subgrids (e.g., rows, columns, or 3x3 blocks) prunes inconsistent partial assignments early, enhancing propagation without exhaustive search.Advanced Consistency Notions
Directional Consistency
Directional consistency is a local consistency notion in constraint satisfaction problems (CSPs) that leverages a specific ordering of variables to ensure efficient constraint propagation in a forward direction, from earlier to later variables in the ordering. Given a total ordering d = (x_1, x_2, \dots, x_n) of the variables, a CSP is said to be i-directionally consistent if every partial assignment to the first i variables in the ordering can be extended to a value for the (i+1)-th variable that satisfies all relevant constraints involving those variables.[18] This property guarantees that backtracking is unnecessary when instantiating variables sequentially along the ordering up to i+1, provided the induced width of the constraint graph aligns with the consistency level.[19] Key variants include directional arc consistency (DAC), which corresponds to 2-directional consistency, and directional path consistency (DPC), which corresponds to 3-directional consistency. DAC enforces that for every ordered arc (x_i \to x_j) with i < j, each value in the domain D(x_i) has at least one supporting value in D(x_j) that satisfies the binary constraint between x_i and x_j, considering the directional ordering.[18] Formally, a CSP is directionally arc-consistent under ordering d if for all variables x, y with x < y in d, the directed arc from x to y is arc-consistent, meaning \forall a \in D(x), \exists b \in D(y) such that (a, b) satisfies the constraint C(x, y).[20] DPC extends this by ensuring consistency over paths of length 2, requiring that every pair of values for earlier variables has a supporting value in a later variable connected to both.[21] These variants assume a fixed variable ordering, which influences the constraint graph's induced structure. The primary advantage of directional consistency lies in its reduced computational overhead compared to undirected counterparts like full arc or path consistency, as it avoids symmetric enforcement and focuses propagation forward, eliminating redundant checks.[18] For instance, achieving DAC requires O(ek^2) time, where e is the number of arcs and k the domain size, versus O(ek^3) for standard arc consistency.[18] This efficiency enables backtrack-free search on tree-structured CSPs (width 1) via DAC and on width-2 graphs via DPC, making it foundational for algorithms like bucket elimination that exploit orderings to solve CSPs optimally relative to the graph's induced width.[19]Relational Consistency
Relational consistency is a relation-based form of local consistency in constraint satisfaction problems (CSPs), where the primitive entities are the constraint relations rather than individual variables. Introduced by Dechter and van Beek (1997), it generalizes traditional variable-based consistencies (like k-consistency) to networks with constraints of arbitrary arity. Relational m-consistency requires that for any variable x and any set of m-1 relations R_{S_1}, \dots, R_{S_{m-1}} whose scopes S_i all include x, every consistent partial assignment to the variables A = \bigcup S_i \setminus \{x\} can be extended to a value for x such that the full assignment satisfies all m-1 relations simultaneously. Formally, \varsigma(A) \subseteq \pi_A (\bowtie_{i=1}^{m-1} R_{S_i}), where \varsigma(A) denotes the set of consistent instantiations of A, and \pi_A is the projection onto A.[22] This property unifies constraint processing operations such as projection, join, and variable elimination within a relational algebra framework, making it suitable for non-binary constraints. Enforcement algorithms include relational-consistency (RC_m), a brute-force method using extended m-composition, and adaptive-relational-consistency (ARC_m), which achieves global consistency with time complexity O(n \cdot \exp((n+e) w^*(d))), where n is the number of variables, e the number of constraints, and w^*(d) the induced width under ordering d. A directional variant, DRC_m, propagates consistency forward along an ordering with complexity O(\exp(m w^*(d))).[22] In contrast to variable-centric approaches, which focus on extending assignments to individual variables, relational consistency treats entire relations as units, providing a more natural handling of high-arity constraints and linking local properties to global solvability via treewidth. It complements directional methods by offering an order-independent perspective, though directional extensions like DRC_m combine both paradigms for efficient solving.[22]Algorithms for Enforcing Consistency
Constraint Propagation Techniques
Constraint propagation techniques form a cornerstone of solving constraint satisfaction problems (CSPs) by iteratively pruning variable domains to enforce local consistency, thereby reducing the effective search space and detecting inconsistencies early. These methods operate by maintaining a queue of constraints or arcs (variable pairs connected by binary constraints) that require revision; when a domain is reduced, affected arcs are enqueued for processing. Revision involves checking each value in a domain for support in neighboring domains and removing unsupported values, repeating until a fixed point is achieved where no further changes occur. Propagation is typically triggered by events such as variable assignments or domain reductions that violate constraints, enabling dynamic adaptation during search.[23] This queue-based approach, rooted in early consistency algorithms, ensures efficient handling of dependencies without exhaustive enumeration.[6] A fundamental technique is forward checking, which provides a lightweight form of propagation akin to basic arc consistency during backtracking search. After assigning a value to a variable, forward checking immediately prunes domains of all unassigned future variables connected by constraints, removing values lacking support from the current assignment. Introduced by Haralick and Elliott in 1980, this method anticipates deeper search failures by focusing only on forward constraints, avoiding full network revision.[24] It operates with a time complexity of O(ed^2) per assignment in the worst case, where e is the number of constraints and d the maximum domain size, but empirically reduces backtracks significantly on problems with tight constraints.[24] Maintaining arc consistency (MAC) builds on forward checking by fully enforcing arc consistency after each assignment, using optimized revision algorithms like AC-3 to propagate changes across the entire remaining network. In MAC, arc consistency ensures every value in a domain has a supporting value in each neighboring domain, achieved by queuing and revising all affected arcs until stability. Sabin and Freuder demonstrated that MAC outperforms forward checking by reducing the search tree size, often exploring fewer than 1% of nodes on structured benchmarks like scene labeling problems, due to more aggressive pruning.[25] The overall complexity during search remains polynomial per node but scales with network density, yielding empirical speedups of up to two orders of magnitude in solver performance on random and structured CSPs.[25] For higher-order consistencies like path consistency, specialized propagators such as PC-3 extend the queue-based paradigm to ternary relations formed by paths of length two. PC-3 revises value pairs in a domain by ensuring support through a common intermediary variable, using support lists to track valid combinations and avoid redundant verifications, similar to AC-4's approach for arcs. Developed by Mohr and Henderson in 1986, PC-3 achieves path consistency with a time complexity of O(e d^3), improving over prior algorithms by minimizing constraint checks.[26] This enables pruning of incompatible value pairs, further contracting the search space, though at higher computational cost than arc-level methods. Recent enhancements include singleton arc consistency (SAC), which strengthens propagation by temporarily reducing each variable to a singleton domain and enforcing arc consistency on the resulting network, pruning original values that lead to inconsistencies. This detects near-inconsistencies invisible to standard arc consistency, as each value is tested for viability in isolation. Prosser's 2000 analysis showed SAC solves all tree-structured CSPs and provides empirical benefits on sparse random problems, reducing search nodes by up to 50% in preprocessing, though it incurs O(n e d^3) time where n is the number of variables.[27] SAC is particularly effective in modern solvers for identifying global inconsistencies early without full search.[27] These propagation techniques are applied to enforce arc and path consistencies dynamically during CSP solving.Bucket Elimination
Bucket elimination is an algorithm for enforcing higher-order consistency in constraint satisfaction problems (CSPs) through variable elimination ordered from a specified sequence.[28] It organizes constraints into buckets associated with each variable and processes them sequentially, generating new constraints that summarize the eliminated variables' impacts on the remaining ones.[28] The formal steps of bucket elimination are as follows:- Select a variable ordering d = (X_1, X_2, \dots, X_n), where variables are eliminated from X_n to X_1.
- For each variable X_i, form bucket B_i by placing all original constraints (or functions) that involve X_i as their highest-indexed variable according to d.
- Process the buckets in reverse order, from i = n down to i = 1: Within B_i, compute the relational join (natural join) of all functions in the bucket, then project out X_i via existential quantification to produce a new function over the remaining variables in the join; add this new function to the buckets of those remaining variables (typically the lowest one).