Constraint Propagation¶
Constraint-reasoning method — instantiates Bounded Search Pruning
Pushes known constraints through the remaining choices until some branch's options are emptied, proving it infeasible before anyone searches it.
Constraint Propagation prunes without ever comparing anything to anything. It takes the hard constraints of a problem and pushes their consequences through the network of undecided variables: fixing one choice narrows the legal values of its neighbors, which narrows their neighbors, and so on. When propagation drives some variable's set of legal values to empty, the branch that led there has been proven infeasible — not unpromising, impossible — and is dropped before any search descends into it. The one idea that makes this mechanism itself is that exclusion is deductive and feasibility-only: it needs no objective to optimize, no front-runner to beat, and no candidate to rank. It reasons purely about what the constraints force, re-firing whenever a new choice or constraint tightens the picture.
Example¶
A university is building next term's exam timetable: hundreds of exams into a fixed grid of rooms and slots, under hard rules — no student sits two exams at once, no room is double-booked, large exams need large halls. Rather than trying schedules and checking them, the scheduler propagates. Assign the biggest exam to the one hall that fits it, and propagation immediately strikes that slot from every exam sharing students with it, and strikes that hall from every overlapping exam. Each of those removals cascades further. At one point propagation leaves a mid-size exam with no legal (room, slot) pair remaining — an empty domain. That proves the branch of assignments made so far cannot be completed into any valid timetable, so the scheduler discards it and backtracks, never enumerating the thousands of dead schedules beneath it. Whole regions of the space are eliminated by deduction, long before a single complete timetable is scored.
How it works¶
- State the constraints, not an objective. Feasibility rules — mutual exclusions, capacities, precedences — are the whole input; there is no score to maximize.
- Propagate consequences. Each decision or new fact removes now-illegal values from connected variables; those removals cascade until the network settles (reaching a form of consistency).
- Detect the wipeout. If any variable's legal set is emptied, the current branch cannot be completed feasibly — prune it.
- Re-fire on change. Every time a variable is fixed or a constraint tightens, propagation runs again over the affected region, so the feasible picture stays current as the search descends.
Tuning parameters¶
- Consistency strength — how hard propagation pushes (from cheap bounds-checking up to full arc consistency). Stronger propagation prunes more infeasible branches[1] but costs more at every step.
- Propagation scope — re-check only the variables touched by a change, or sweep the whole network. Local re-checking is fast; global sweeps catch more but cost more.
- Trigger granularity — how often the re-fire fires: after every assignment, or batched. Frequent re-firing keeps the feasible set tight but adds overhead.
- Constraint completeness — how many of the real rules are actually encoded. Every omitted constraint is a region propagation cannot prune — and a source of infeasible branches that survive.
When it helps, and when it misleads¶
Its strength is that it kills infeasible regions by pure deduction, before any evaluation cost is paid, and it does so without needing an objective — ideal for tightly constrained combinatorial problems where most of the space is illegal rather than merely bad. It shrinks what any later optimizer even has to look at.
It misleads when the encoded constraints do not match the real ones. Propagation is only ever sound with respect to the constraints it was given; if a genuine constraint was left out of the model, propagation will happily leave infeasible branches alive, and — more dangerously — if a spurious constraint was put in, it will prune branches that were actually valid, wiping out real solutions with total deductive confidence. The classic misuse is trusting a rich, fast-propagating model without checking that its constraints faithfully mirror the problem. The guarding discipline is to validate the constraint set against reality first, and to treat an "infeasible" verdict as only as trustworthy as the rules that produced it.
How it implements the components¶
objective_and_constraint_reference— the feasibility constraints are its entire working input; propagation is the act of enforcing them across the variable network.pruning_rule— a branch is excluded exactly when propagation empties some variable's legal-value set: proven infeasible, so dropped.bound_refresh_trigger— each new assignment or tightened constraint re-fires propagation over the affected region, keeping the feasible picture current as the search moves.
It keeps no incumbent_solution and does no score comparison — that is Bound-Based Candidate Screening — and it does not decide when a case-level branch should be revisited because the real situation changed, which is the branch_reopening_rule of Diagnostic Tree Pruning. Propagation deduces infeasibility; it does not weigh or re-open.
Related¶
- Instantiates: Bounded Search Pruning — Constraint Propagation supplies the feasibility-side pruning: branches deduced to be impossible are removed before search.
- Sibling mechanisms: Admissible Heuristic Search · Bound-Based Candidate Screening · Diagnostic Tree Pruning · Dominance Filtering · Legal Issue Pruning Matrix · Pruning Audit Log · Branch and Bound · Feasibility Certificate Check
Editorial Notes¶
Form Classification¶
Form family: Analysis, Modeling & Optimization
Rationale: Pushes known constraints through the remaining choices until some branch's options are emptied, proving it infeasible before anyone searches it, making its operative form a computation, comparison, model, or analytic representation used to infer, estimate, or choose.
Independent corroboration: The frozen evidence defines Constraint Propagation as 'Pushes known constraints through the remaining choices until some branch's options are emptied, proving it infeasible before anyone searches it', so its operative form is Analysis, Modeling & Optimization.
Review outcome: Independent reviewer agreement; high confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Single lineage
Present-day reach: Specialized
Rationale: Constraint-programming research cohered propagation of local restrictions through variable domains to prune infeasible branches before search.
Related originating lineages:
- Mathematics — Formal logic supplies deductive consequence and proof of infeasibility by an empty domain.
- Operations Research — Feasibility reasoning and presolve independently use implied constraints to reduce optimization models.
Review resolution: Constraint programming is the clear disciplinary home; logic and optimization presolve are genuine antecedent and parallel lineages, not evidence of broad domain reach.
Review outcome: Reconciled after independent review; high confidence.
Notes¶
Constraint Propagation derives infeasibility by reasoning; Feasibility Certificate Check verifies an infeasibility supplied by someone else. The two are natural partners: propagation can emit the contradiction it discovers as a compact certificate, which a separate checker then trusts without re-deriving — cheap proof on one side, cheap verification on the other.
References¶
[1] Dechter, R. Constraint Processing. Morgan Kaufmann (2003). Explains that stronger consistency propagation can remove more inconsistent values or branches before search. registry ↩