Constraint Satisfaction Search¶
Method — instantiates Discrete Commitment Optimization
Explores the space of discrete combinations to find any assignment that violates no constraint, driven by feasibility rather than an objective.
Constraint Satisfaction Search treats a discrete decision as a puzzle rather than an optimization: there is a set of variables, each with a small domain of allowed values, and a web of constraints saying which value-combinations are legal — and the goal is simply to find a complete assignment that breaks none of them. It carries no objective function. Nothing is "better"; a candidate is either feasible or it is not. Its defining move is propagation-and-backtracking: fix a variable, immediately narrow every other variable's options through the constraints that touch it, and back out the moment a variable's domain empties. Where the optimizing siblings ask "which feasible bundle is best?", this method answers the prior and often harder question — "does any feasible bundle exist, and can you show me one?"
Example¶
A university registrar must schedule 220 final exams into a week of five days and eight rooms. The rules are unforgiving: no student sits two exams at once, no room holds two exams in the same slot, large-enrollment exams need the big hall, and a handful of exams have a fixed regulatory time. There is no notion of an "optimal" timetable here — the administration just needs one that works, and every prior attempt by hand collapsed under a late-surfacing clash.
The registrar models each exam as a variable whose domain is the legal (day, slot, room) triples. A conflict graph links every pair of exams that share even one student. Search then assigns exams one at a time; each assignment prunes the domains of its graph neighbors, and when an exam's domain goes empty the search backtracks and tries a different slot for the exam it placed just before. After exploring a fraction of the astronomically large raw space, it returns a complete clash-free timetable — or, just as usefully, proves that under the current room stock no feasible timetable exists, which tells the registrar to add a room rather than keep hunting.
How it works¶
- Declare variables, domains, and constraints. Each decision unit gets a finite domain; each rule becomes a constraint linking a few variables.
- Build the constraint graph and propagate. Every time a value is fixed or eliminated, tighten the domains of neighboring variables — arc-consistency techniques kill doomed branches before they are ever searched.[1]
- Search with backtracking. Assign, propagate, and recurse; on a dead end (an emptied domain) unwind the last choice and try the next. Variable- and value-ordering heuristics decide what to try first.
- Certify or refute. Return the first complete legal assignment, or — having exhausted the pruned tree — report that none exists.
The method's whole engine is feasibility bookkeeping; it never compares two legal solutions, because it has no yardstick to compare them with.
Tuning parameters¶
- Propagation strength — from cheap forward-checking to full arc- or path-consistency. Stronger propagation prunes more per step but costs more per step.
- Variable-ordering heuristic — e.g. most-constrained-first. Good ordering can shrink search by orders of magnitude; a poor one thrashes.
- Restart / randomization policy — whether to abandon and restart a stuck search from a shuffled ordering, trading determinism for robustness on hard instances.
- Stop-on-first vs. enumerate — halt at one solution, or enumerate the feasible set for downstream ranking. Enumeration is far costlier and only worth it when something else will choose among the results.
When it helps, and when it misleads¶
Its strength is finding a needle in a combinatorial haystack — and, equally, proving the haystack has no needle, which spares a team from optimizing a problem that was infeasible all along. It excels at hard-constraint tangles (timetabling, configuration, puzzle-like resource fits) where the pain is finding any legal arrangement at all.
Its failure mode is precisely the missing objective: it returns a feasible answer, not a good one, so if quality actually matters, using bare satisfaction quietly ships whatever the search happened to stumble on first. A related misuse is over-hardening — encoding a soft preference ("prefer morning exams") as a hard constraint, which can turn a solvable problem infeasible and send the search chasing a solution that never existed. The guarding discipline is to keep hard constraints and soft preferences strictly separate: satisfy the hard ones here, then hand the feasible result to an optimizing or deliberative mechanism if quality is at stake.
How it implements the components¶
combinatorial_feasible_set— it operates directly on this set, walking the legal-combination space that satisfies every hard constraint.feasibility_audit— constraint checking is not a post-step but the search's inner loop; every partial assignment is continuously audited.dependency_graph— the constraint graph linking variables that share a rule is what propagation walks to prune domains.cardinality_limit— "at most/at least k values in this group" constraints (one exam per slot, minimum coverage) are enforced as first-class constraints.
It does not implement objective_function — a pure feasibility search has no notion of a best bundle; scoring and optimizing belong to Integer Programming Model. Nor does it build the assignment_compatibility_matrix that is Assignment Model's signature.
Related¶
- Instantiates: Discrete Commitment Optimization — it supplies the feasibility-search variant, answering existence before optimality.
- Sibling mechanisms: Assignment Model · Crew Scheduling Model · Facility Location Model · Integer Programming Model · Integer Programming Solver · Project Selection Matrix · Selection Review Board · Solver Dashboard
Editorial Notes¶
Form Classification¶
Form family: Analysis, Modeling & Optimization
Rationale: Explores the space of discrete combinations to find any assignment that violates no constraint, driven by feasibility rather than an objective, making its operative form a computation, comparison, model, or analytic representation used to infer, estimate, or choose.
Independent corroboration: The frozen evidence defines Constraint Satisfaction Search as 'Explores the space of discrete combinations to find any assignment that violates no constraint, driven by feasibility rather than an objective', 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: Cross-disciplinary synthesis
Present-day reach: Specialized
Rationale: Artificial-intelligence and constraint-programming research cohered propagation-and-backtracking search for any complete assignment satisfying a discrete constraint set.
Related originating lineages:
- Mathematics — Combinatorics and logic supply the finite assignment and satisfiability foundations.
- Operations Research — Feasibility programming supplies adjacent discrete-model methods without requiring an objective function.
Review resolution: AI constraint programming is primary, but discrete mathematics and operations-research feasibility are constitutive co-lineages, supporting synthesis rather than a purely isolated computer-science lineage.
Review outcome: Reconciled after independent review; high confidence.
References¶
[1] Arc consistency (e.g. Mackworth's AC-3, 1977) prunes from each variable's domain any value that has no compatible partner in a neighboring variable — a constraint-propagation step that removes doomed branches before the search ever visits them. withdrawn registry ↩