Constraint Propagation Networks

Origin. FGCP constraint logic programming research; CLP(R), CLP(FD) systems; Concurrent Constraint Programming (Saraswat, influenced by FGCP concurrent logic work).

Mechanism. Variables are constrained rather than assigned. Constraints propagate: when one variable's domain shrinks, the constraints it participates in may shrink other variables' domains. The network reaches a fixed point when no constraint can propagate further. If a domain becomes empty, the constraint set is unsatisfiable. If all domains are singletons, a solution is found. Otherwise, search splits a domain and propagates again.

Procedure. Model the problem as variables with domains and constraints between them. Establish arc consistency: for each constraint, remove values from each variable's domain that have no supporting value in the other variables. Propagate until fixed point. If not solved, select a variable and split its domain (branching). Propagate again. Backtrack if a domain empties.

Applies to. Scheduling, resource allocation, configuration, and any combinatorial problem where constraints are local but solutions are global.

Limitations. Propagation strength varies by constraint type; some constraints propagate weakly and leave large domains. The branching heuristic dominates performance, and no universal heuristic exists. Also: modeling the problem as constraints is itself the hard part; an over-constrained model has no solutions, an under-constrained model has too many, and distinguishing these from bugs in the constraint formulation is difficult.