Constraint Propagation and Inference

Core Idea

Constraint propagation uses constraints to reduce the domains of variables, potentially making future search choices trivial or revealing inconsistencies early. The key insight: inference before and during search eliminates work that backtracking would otherwise have to do.

Levels of Consistency

Node Consistency

A variable Xᵢ is node-consistent if every value in Dᵢ satisfies Xᵢ’s unary constraints. - Trivially achieved as preprocessing; just filter each domain.

Arc Consistency

Variable Xᵢ is arc-consistent with respect to Xⱼ if for every value x ∈ Dᵢ there exists some value y ∈ Dⱼ satisfying the binary constraint Cᵢⱼ.

A CSP is arc-consistent (AC) if every variable is arc-consistent with every other variable it shares a constraint with.

Key point: AC can reduce domains to empty (detecting infeasibility) or to singletons (determining values with no search at all).

Path Consistency

Three variables Xᵢ, Xⱼ, Xₖ are path-consistent if for every consistent assignment of Xᵢ and Xₖ, there is a value for Xⱼ consistent with both. Stronger than arc consistency but rarely used in practice (cubic cost).

k-Consistency

A CSP is k-consistent if for any consistent assignment of k−1 variables, a consistent value can always be found for any kth variable. - 1-consistent = node consistent - 2-consistent = arc consistent - 3-consistent = path consistent

Strong k-consistency: k-consistent for all j ≤ k. If a CSP is strongly n-consistent (n = #variables), it can be solved without backtracking — but achieving it is as hard as solving the problem.

AC-3 Algorithm

The standard arc-consistency algorithm. Maintains a queue of arcs to check; when a domain is reduced, re-adds affected arcs.

function AC-3(csp) returns false if inconsistency found, true otherwise
    queue ← all arcs (Xᵢ, Xⱼ) in csp
    while queue is not empty do
        (Xᵢ, Xⱼ) ← REMOVE-FIRST(queue)
        if REVISE(csp, Xᵢ, Xⱼ) then
            if size of Dᵢ = 0 then return false   // domain wipe-out
            for each Xₖ in NEIGHBORS(Xᵢ) − {Xⱼ} do
                add (Xₖ, Xᵢ) to queue
    return true

function REVISE(csp, Xᵢ, Xⱼ) returns true iff domain of Xᵢ was revised
    revised ← false
    for each x in Dᵢ do
        if no value y in Dⱼ satisfies constraint Cᵢⱼ(x, y) then
            delete x from Dᵢ
            revised ← true
    return revised

Complexity of AC-3

• Each arc (Xᵢ, Xⱼ) can be re-inserted at most d times (once per deletion from Dᵢ)
• REVISE costs O(d²) per call
• Total: O(c · d³) where c = number of binary constraints, d = max domain size

What AC-3 Guarantees

• Does guarantee: No arc-inconsistent value remains in any domain.
• Does NOT guarantee: A solution exists. AC-3 is not complete — may leave non-singleton domains with hidden inconsistencies requiring backtracking.

Global Constraints

Alldiff

Alldiff(X₁, …, Xₙ) — all variables must take distinct values.

Efficient enforcement via bipartite matching: 1. Build bipartite graph: variables on left, domain values on right. 2. Find a maximum matching. 3. If matching size < n, constraint is unsatisfiable. 4. Remove any edge not in any maximum matching — those (variable, value) pairs cannot be part of any solution.

Runs in O(n · d) time; far better than converting to O(n²) binary ≠ constraints.

Atmost / Resource Constraints

Atmost(k, X₁, …, Xₙ, v) — at most k of the Xᵢ can equal value v. Useful in scheduling (at most k jobs per machine slot).

Bounds Consistency (for Integer Domains)

Instead of checking each value, maintain only [min, max] bounds. Variable Xᵢ is bounds-consistent with Xⱼ if: - There exists a y ∈ [minⱼ, maxⱼ] consistent with x = minᵢ - There exists a y ∈ [minⱼ, maxⱼ] consistent with x = maxᵢ

Much cheaper than full arc consistency for large integer domains (e.g., scheduling).

Forward Checking vs. MAC

MAC is the standard approach: after assigning Xᵢ = v, run AC-3 starting from all arcs (Xⱼ, Xᵢ) for each neighbor Xⱼ.

Propagation Hierarchy

Increasing power (and cost):
Node consistency → Arc consistency (AC-3) → Path consistency → k-consistency
     O(n·d)             O(c·d³)               O(n³·d³)          exponential
                            ↑
                    AC-3 / MAC: sweet spot in practice

Key Takeaway

Constraint propagation is not search — it’s inference. It eliminates values that cannot participate in any solution, reducing the effective search space before a single backtracking step is taken. MAC combines this inference with search, running AC-3 at every node of the search tree.