Does propagation choose a preferred value?

Not inherently. It removes or restricts values that cannot satisfy the current conditions; preference and search choices are separate mechanisms.

Does reaching a fixed point prove there is a solution?

No. It only means the selected propagators cannot currently narrow the domains further.

Why revisit a constraint already checked?

Another constraint may have changed a shared variable's domain, removing support that existed during the earlier check.

AI Glossary / Graphs and symbolic AI / Intermediate

Constraint propagation

Definition

Constraint propagation uses known restrictions to derive further restrictions on variable values. When one variable's domain changes, related constraints can reduce other domains, and those reductions can trigger further reasoning. The process helps eliminate impossible choices before or during search while preserving solutions under the stated constraint model.

What it means

A domain is the set of values a variable may take. A constraint specifies which combinations are allowed. Propagation connects them: if a value no longer has the support needed to satisfy a constraint, a sound propagator can remove it.

The operation differs from making a guess. Assigning a trial value chooses one branch of a search. Propagation derives consequences of the current constraints and assignments without selecting an unsupported alternative.

Different propagators enforce different levels of reasoning. Some maintain bounds, others inspect individual domain values, and specialized global constraints can derive consequences from several variables together. Reaching a stable set of domains means the selected propagators have no further changes to make, not necessarily that all consequences have been discovered.

How it works

The solver initially places relevant constraints on a processing agenda. A propagator examines a constraint and the current domains, then removes values or tightens bounds that cannot satisfy its reasoning condition.

If a domain changes, other constraints involving that variable may need reconsideration. This repeats until no scheduled propagator can make further progress, a domain becomes empty, or another stopping condition applies.

An empty domain demonstrates failure under the current branch assumptions, provided the propagation steps were sound. Nonempty domains do not generally prove that a complete solution exists.

Search can then choose a variable and value, propagate that choice, and backtrack if necessary. On backtracking, reductions dependent on the abandoned choice must be restored appropriately. The combination of propagation and search can be much stronger than either naive enumeration or one isolated pass through the constraints.

Three practical examples

1. A scheduling model tightens a task's earliest start after a predecessor's duration changes, then passes that restriction to subsequent tasks.

2. A configuration solver removes component options that no longer have a compatible partner in another component's remaining domain.

3. An arithmetic model narrows possible integer values from equations and inequalities before a search enumerates any complete assignments.

Think of it this way

Think of propagation as a network of connected restrictions: tightening one link can tighten others until the available slack stops changing.

The analogy has limits. Formal propagators apply defined reasoning rules, and some constraints may yield no local reduction even when their combination has no solution. A stable network of domains is not automatically a solved problem.

Worked example

Let X, Y, and Z be integers, initially each in {1, 2, 3, 4}. Require X less than Y and Y less than Z.

From X less than Y, X cannot be 4 because Y has no larger value, and Y cannot be 1 because X has no smaller value. From Y less than Z, Y cannot be 4 and Z cannot be 1 or 2 once Y's minimum is 2.

Revisiting the first constraint now shows that X cannot be 3: Y's maximum is 3, and X must be strictly smaller. At a stable point, the domains are X in {1, 2}, Y in {2, 3}, and Z in {3, 4}.

These domains still do not mean all combinations are allowed. For example, X = 2 and Y = 2 violates the first constraint. The constraints remain active alongside the domains.

If a search next chooses Z = 3, propagation forces Y = 2 and then X = 1. No guessing is needed for those two consequences. The deductions use integer domains and strict inequalities; a different domain or relation would produce different results.

Illustrative case study

Fictional case: Pine Planning demonstrates the three-variable chain. Its first implementation processes each constraint once and stops, leaving X = 3 in its domain after Y has already been reduced.

The reviewer observes that a later domain change can invalidate earlier support. The solver's agenda is updated so affected constraints are revisited. The team then checks the stable domains and the consequences of fixing Z = 3.

This case illustrates why propagation is iterative. It does not report a production speedup or claim that the same propagation strength solves every scheduling problem without search.

Common misconceptions and mistakes

Do not assume propagation is equivalent to exhaustive search. It can leave unresolved combinations even when every remaining individual value has local support.

Do not remove a value because it seems unlikely or undesirable unless that is justified by the specified constraints and solver semantics. Sound propagation must preserve genuine solutions.

Do not discard the constraints after narrowing domains: cross-variable relationships remain essential. Also distinguish a domain becoming empty under a trial assignment from proof that the original problem, before that trial, is globally infeasible.

Business use

For business teams, propagation explains why a seemingly small requirement change can affect many available choices. It can make a configurator respond quickly to selections or help a solver avoid exploring branches that are already impossible.

The quality of the result depends on the model and the strength of its propagators. Review which deductions are guaranteed, whether a reported failure is local or global, and what search remains. Stronger propagation can reduce search but require more work per update, so the best balance depends on the workload.

Check your understanding

After propagation, X and Y both include 2 in their domains, but the model requires X less than Y. Is X = 2, Y = 2 valid?

Answer: No. Individual domain membership is insufficient; the joint assignment must still satisfy the retained constraint.

Related terms

Fixed point
Forward checking
Global constraint
Domain reduction
arc consistency
bounds consistency
propagator
backtracking

Learn next

Trace the worked chain with an agenda of affected constraints and record every domain change. Then compare bounds propagation with value-level arc consistency, and study a case where local consistency still requires search to determine solvability.

Sources

Russell and Norvig, Artificial Intelligence: A Modern Approach, Constraint Satisfaction Problems: https://aima.cs.berkeley.edu/2nd-ed/newchap05.pdf ; SWI-Prolog official CLP(FD) documentation: https://www.swi-prolog.org/man/clpfd.html . Relevant primary explanations of propagation and constraint reasoning were consulted. The integer chain and fictional agenda bug are original teaching examples.

Previous: Constraint logic programming Next: Constraint satisfaction