Strong Local Consistency for Constraint Satisfaction

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 221 papers23 conceptsfrozen 2026-10-04

In constraint satisfaction problems (CSPs), the goal is to find a set of assignments that satisfy all requirements simultaneously. Most solvers rely on local consistency—the idea that we can prune the search space by looking at constraints in isolation. However, as Christian Bessiere and others have argued, evaluating constraints independently often misses the "big picture," leading solvers into massive, redundant search trees.

The research direction of Strong Local Consistency focuses on bridging the gap between local checks and global validity by reasoning about the interactions between multiple constraints.

The Limits of Isolation

Standard techniques like Arc Consistency (AC) or Bounds Consistency (BC) operate locally. They look at a single constraint and a single variable's domain to see if any values are obviously impossible.

The problem, as noted by John N. Hooker in Projection, Inference, and Consistency, is that this "domain consistency" ignores interdependencies. A value might look fine for Constraint A and fine for Constraint B, but be impossible when A and B are considered together. This localized focus is why solvers often backtrack: they don't realize a choice is doomed until they are deep in the search tree.

Reasoning Across Intersections

To solve this, researchers developed "higher-order" consistencies that look at clusters of constraints. Instead of treating a problem as a collection of independent rules, these methods treat it as a network of overlapping relations.

  1. Global Constraints: Kostas Stergiou 0001 and Toby Walsh demonstrated in The Difference All-Difference Makes that treating a set of "not-equal" constraints as a single "AllDifferent" entity provides vastly superior pruning power. By looking at the global requirement, the solver can detect contradictions that are invisible to binary checks.
  2. Relational Consistency: Rather than just filtering variable domains, algorithms like $R(*,m)C$ filter the relations themselves. Shant Karakashian and Berthe Y. Choueiry showed that by enforcing consistency across $m$ relations, solvers can often become "backtrack-free," solving complex benchmarks without ever making a wrong turn.
  3. Intersecting Table Constraints: In An Efficient Higher-Order Consistency Algorithm for Table Constraints, Anastasia Paparrizou and Kostas Stergiou 0001 introduced maxRPWC+, which specifically exploits the variables shared between intersecting constraints to prune values that standard methods would miss.

Shaving and Singleton Consistency

Another way to achieve strong consistency is through "shaving" or "singleton" tests. The intuition is simple: "What would happen if I actually picked this value?"

Olivier Lhomme and Jean-Charles Régin proposed Quick Shaving, which uses search failures as an oracle to predict which values to test. If a tentative assignment leads to an immediate contradiction, that value can be permanently removed.

While powerful, these tests are computationally expensive. To manage this, Amine Balafrej and colleagues developed APOAC (Adaptive Singleton-Based Consistencies), which dynamically learns which singleton tests are likely to be productive, applying strong inference only where it is most needed.

From Local to Global

The ultimate goal of this research is to identify when local consistency is sufficient to guarantee a global solution. Peter van Beek identified structural properties like row convexity that allow polynomial-time algorithms to solve otherwise NP-complete problems. Similarly, Yuanlin Zhang 0002 and Roland H. C. Yap developed frameworks to derive global consistency from local set intersections.

Interestingly, stronger isn't always "more." Avi Dechter and Rina Dechter argued that removing redundant constraints can be just as important as adding new ones. By simplifying the "connective structure" of the network, we can make the underlying graph sparser and more manageable for search algorithms.

Summary of Intuition

Strong local consistency works because it acknowledges that constraints do not exist in a vacuum. By reasoning about conjunctions (Bessiere), neighborhoods (Robert J. Woodward), and intersections (Paparrizou), these algorithms detect "deep" contradictions early. This shifts the computational burden from the exponential uncertainty of backtracking search to the more predictable, polynomial-time overhead of advanced inference.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 28 papers
  2. Version 1 · 2026-10-04 · 21 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_local_consistency_limitations_362aee2e,
  title = {local consistency limitations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/local-consistency-limitations/rdr_362aee2e8e5e448783642359e77e3bc4},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_strong_local_consistency_for_constraint__362aee2e_v1,
  title = {Strong Local Consistency for Constraint Satisfaction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/strong-local-consistency-for-constraint-satisfaction/rdr_362aee2e8e5e448783642359e77e3bc4/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}