## Definition **Constraint propagation** is the general technique of reducing the domains of CSP variables by deducing logical consequences of constraints, *without* committing to specific assignments. The umbrella term that includes [[Arc Consistency AC-3]] and many specialised algorithms for global constraints. ## The Core Idea Given a partial state of variable domains, propagation asks: *which values can I rule out based on current information, before any search step?* Removing values is "free" (no commitment) but compounds: removing a value from $D_i$ may make some value in $D_j$ unsupported, which may trigger more removals — a cascade through the constraint graph. ## Levels of Consistency - **Node consistency.** Each unary constraint is satisfied by every value in the domain. - **Arc consistency.** Every binary constraint is arc-consistent. See [[Arc Consistency AC-3]]. - **Path consistency (3-consistency).** For every consistent 2-tuple, there exists a value at any third variable consistent with both. - **k-consistency.** Extends to k-tuples. Higher consistency catches more failures earlier — at the cost of computation. The sweet spot is usually arc consistency for general CSPs, plus specialised propagators for global constraints. ## Global Constraint Propagators Global constraints have *specialised* propagation algorithms that exploit structure: - **AllDifferent** — bipartite matching algorithm (Régin 1994) for GAC in polynomial time. - **Cumulative** — for scheduling with resource constraints; time-table propagation. - **GCC (Global Cardinality Constraint)** — for assignments where each value can appear within a count range. - **Element** — array indexing constraints. A modern CP solver may have 50+ such global constraints, each with custom propagation logic. ## Propagation Engines The orchestration of which propagators fire when: - **Fixed-point computation.** Run propagators until no domain changes. - **Priority queues.** Cheap propagators run first. - **Watched-literals** style — propagators wake only when relevant variables change. ## Integration with Search Propagation alone usually doesn't solve a CSP — it must be combined with search. The typical loop: 1. Propagate to fixpoint. 2. If any domain is empty → backtrack. 3. If all variables fixed → solution. 4. Otherwise, branch on a variable; recurse. ## Why It's Decisive in Modern Solvers The combination of strong propagation + conflict-driven backjumping + restart strategies turns even NP-hard CSPs into tractable problems for most industrial instances. The success of solvers like CP-SAT (Google OR-Tools) is largely propagation engineering. ## Related - [[Constraint Satisfaction Problem]] - [[Arc Consistency AC-3]] - [[Backtracking Search]]