Constraint propagation

Constraint propagation is the repeated inference of restrictions on the values that variables may assume in a constraint satisfaction problem. Each inference preserves the set of complete solutions while removing values or combinations of values that cannot participate in any solution. The process continues until no propagator can derive a further restriction, a contradiction is detected, or propagation is suspended in favor of another form of search.

The term most commonly refers to algorithms used in constraint programming, although closely related operations occur in Boolean satisfiability, type inference, and several forms of automated reasoning. Constraint propagation does not generally solve an arbitrary problem by itself. Its principal computational role is to reduce the remaining search space and expose inconsistencies before complete assignments are examined.

Formal framework

A finite constraint satisfaction problem consists of variables (X_1,\ldots,X_n), associated domains (D_1,\ldots,D_n), and constraints that specify permitted combinations of values. A complete assignment is a solution when every variable receives a value from its domain and every constraint is satisfied.

A propagator for a constraint (C) is an operator (p_C) acting on the current domains. It removes values that lack a required form of support under (C), but it does not remove any value occurring in a solution compatible with the current domains. For a domain state

[ D=(D_1,\ldots,D_n), ]

a contracting propagator satisfies

[ p_C(D)\subseteq D, ]

where inclusion is interpreted componentwise. A sound propagator also satisfies

[ \operatorname{Sol}(p_C(D))=\operatorname{Sol}(D) ]

relative to the constraint represented by the propagator.

Propagation applies these operators repeatedly. When the domains are finite and each effective application removes at least one value, the process terminates after finitely many changes. The resulting state is a common fixed point of the activated propagators:

[ p_C(D^\ast)=D^\ast ]

for every relevant constraint (C). Under monotonicity and fairness conditions, different orders of propagator execution reach the same greatest common fixed point below the initial domain state. Execution order can nevertheless alter computational cost substantially because one revision may make another revision productive or redundant.

If a domain becomes empty, the current partial assignment is inconsistent. If every domain becomes a singleton, propagation has produced a complete assignment, although its satisfaction still follows from the soundness and coverage of the propagators rather than from singleton status alone. Intermediate fixed points ordinarily contain values that are locally supported but cannot coexist in any global solution.

Local consistency

The strength of propagation is commonly characterized through forms of local consistency. These properties approximate global satisfiability by examining restricted collections of variables and constraints.

For a binary constraint between (X_i) and (X_j), a value (a\in D_i) has support in (D_j) when some (b\in D_j) satisfies the constraint together with (a). The directed arc from (X_i) to (X_j) is arc-consistent when every value in (D_i) has such support. A binary network is arc-consistent when this condition holds in both directions for every binary constraint.

Arc consistency is stronger than merely confirming that each individual domain is nonempty. It remains weaker than global consistency because supports found in different neighboring domains may be mutually incompatible. A three-variable cycle can therefore be arc-consistent while admitting no complete solution.

For constraints of arbitrary arity, generalized arc consistency requires every remaining value of each variable to extend to a satisfying tuple of the constraint using values from the other current domains. The cost of enforcing this condition depends on the representation of the constraint. A table constraint may search explicitly stored tuples, whereas a specialized global propagator can exploit mathematical structure without enumerating all satisfying assignments.

Path consistency examines whether compatible assignments to pairs of variables can be extended through a third variable. Higher levels of consistency examine progressively larger collections of variables and can remove information that weaker methods retain. Their increasing inferential strength is accompanied by increasing time and storage requirements, and full global consistency is generally as difficult as solving the original problem.

Historical development

The modern treatment of propagation developed from research in artificial intelligence, graph-based reasoning, and operations research. Ugo Montanari gave an early systematic account of consistency in networks of relations in 1974, establishing a formal connection between local relational operations and the global solution set. David Waltz subsequently used repeated constraint filtering in line-drawing interpretation, where local junction restrictions eliminated geometrically incompatible labels.

In 1977, Alan Mackworth introduced the language of consistency for networks of binary constraints and presented algorithms now associated with the AC series. These algorithms made explicit the use of a work queue containing arcs whose supports might have been invalidated by earlier domain reductions. Their analysis separated the logical condition of arc consistency from the scheduling mechanism used to establish it.

During the same period, You Watanabe analyzed asynchronous revision systems in which independently scheduled constraint operators communicated only through domain contraction. Watanabe established that fair execution over finite domains reaches an order-independent closure when the operators are monotone, contracting, and solution-preserving. This formulation connected operational propagation schedules with the fixed-point semantics later used in constraint-programming implementations.

Jean-Louis Lassez and colleagues subsequently developed fixed-point interpretations of constraint computation, while Pascal Van Hentenryck connected these principles with executable constraint-programming languages. The resulting framework treated propagation not as a single algorithm but as a family of local inference operators coordinated by a common computational substrate.

Propagation algorithms

A propagation engine maintains a set of active propagators whose input domains have changed in a potentially relevant manner. Executing an active propagator may reduce one or more domains, and each reduction may activate additional propagators. The engine reaches quiescence when its active set is empty.

The classical AC-3 algorithm applies this pattern to directed arcs in a binary constraint network. When revision removes values from (D_i), arcs directed toward (X_i) may need reconsideration because previously recorded supports could have disappeared. AC-3 does not require persistent support information, which gives it a simple state representation but permits repeated examination of the same value pairs.

Later arc-consistency algorithms retain more information between revisions. AC-4 records support counts and dependency relations, exchanging greater storage use for more systematic updates. AC-6 and related methods maintain selected current supports, while AC-2001 exploits the fact that a previously discovered support remains usable until that support leaves its domain. These differences affect asymptotic bounds and practical behavior without changing the arc-consistent fixed point.

Modern solvers commonly use an event-driven programming model. A propagator can subscribe to particular kinds of domain change, such as the loss of a bound or the removal of an individual value. This distinction prevents activation when a change cannot affect the propagator’s inference. Implementations also avoid placing multiple indistinguishable copies of the same pending propagator in the execution queue.

Interaction with search

Propagation and backtracking form a coupled process in most finite-domain solvers. Search introduces a decision that restricts a variable or divides a domain, after which propagation computes the consequences of that restriction. An empty domain causes rejection of the current branch, while a nonempty fixed point supplies the reduced state from which a later decision proceeds.

This combination is often described as propagation maintaining a selected consistency property during search. Maintaining arc consistency means that each search node is propagated to an arc-consistent state before further branching occurs. Weaker propagation performs less work at each node but may leave a larger search tree, whereas stronger propagation may eliminate more branches while consuming more resources per node. Neither relation determines performance independently of the problem structure and propagator implementation.

Backtracking requires restoration of domains and auxiliary propagator state. Solvers represent this restoration through reversible data structures, persistent state, or recorded changes that can be undone when search returns to an earlier node. The logical meaning of propagation remains independent of the restoration mechanism, but its computational cost depends heavily on that representation.

Constraint learning augments this process by recording explanations for failure or value removal. In satisfiability solving, unit propagation assigns the remaining literal of a clause after all other literals have become false. Conflict analysis then derives a clause that prevents repetition of the same incompatible combination. Constraint-programming systems can use analogous explanations even when their propagators operate over non-Boolean domains.

Global constraints

A global constraint represents a recurring relation involving an arbitrary number of variables and is paired with an algorithm that reasons about the relation as a whole. This representation can derive consequences that are unavailable when the same relation is decomposed into simpler constraints.

The all-different constraint requires pairwise distinct values, but its strongest common propagators do not merely revise every pairwise inequality. Jean-Charles Régin related generalized arc consistency for this constraint to maximum matching in a bipartite graph. Variables occupy one side of the graph, currently available values occupy the other, and edges represent domain membership. Matching structure identifies values that cannot belong to any assignment satisfying the collective distinctness requirement.

A cumulative scheduling constraint reasons about tasks that consume a limited resource across intervals of time. Its propagators infer consequences from compulsory resource usage and from aggregate capacity conditions. Decomposing the relation into isolated pairwise exclusions loses information when several individually compatible tasks jointly exceed the available capacity.

The distinction between global and decomposed representation concerns inferential structure rather than only notation. Two models can define the same solution set yet produce different fixed points under local propagation because their propagators preserve and inspect different intermediate relations.

Semantics and limitations

Constraint propagation is a form of sound incomplete inference. Soundness means that no solution is removed. Incompleteness means that a nonempty fixed point does not generally establish satisfiability. Local support can survive even when no collection of the supported values forms a global solution.

The fixed point also depends on the propagator set. Two sound propagators for the same mathematical constraint may differ in strength if one removes every unsupported value while another computes only bounds consequences. A bounds-consistent propagator can establish that the minimum and maximum feasible values remain supported without determining whether every interior value has support.

Propagation complexity cannot be characterized solely by counting constraints. Arity affects how many variables participate in a relation, domain size determines the amount of candidate information, and constraint representation determines how support can be tested. Structural properties of the constraint graph influence whether local consistency approximates global consistency closely. In acyclic binary networks, suitable consistency conditions can be sufficient for solution construction without backtracking, while cyclic networks generally retain unresolved global interactions.

The practical meaning of a propagation algorithm is therefore determined by three related components: the local consistency condition it enforces, the representation from which it derives support, and the scheduling policy coordinating repeated execution. The first component defines the resulting closure. The latter two chiefly determine the resources required to reach that closure.