Constraint Satisfaction Problem (CSP)

CSPs represent problems declaratively, not procedurally. You define what a valid solution looks like, not how to find it. The model consists of:

• Variables (X): A finite set of decision points, e.g., X = {A, B, C}.
• Domains (D): The finite set of possible values for each variable, e.g., D_A = {1, 2, 3}.
• Constraints (C): Relations limiting value combinations, e.g., A > B. This separation of model from algorithm allows a general-purpose solver to process any problem expressed in this format.

In a CSP, the order in which variables are assigned does not affect the final solution's validity. A complete assignment is a set of variable-value pairs; the path taken to reach that set is irrelevant. This property is the fundamental reason why backtracking search can be combined with constraint propagation. Because assignments commute, a solver can:

• Freely reorder variable selection heuristics (e.g., Minimum Remaining Values).
• Interleave search with inference without losing completeness.
• Explore a state space where nodes represent partial assignments, not action sequences.

Before and during search, solvers enforce local consistency to prune impossible domain values. This inference step reduces the search space without branching. Key techniques include:

• Node Consistency: Ensures all values in a unary constraint's variable domain satisfy the constraint.
• Arc Consistency (AC-3): For every binary constraint, every value in the first variable's domain has a supporting value in the second.
• Path Consistency: Extends this logic to triples of variables. Propagation makes NP-hard problems tractable by catching dead-ends early.

When propagation alone cannot solve the problem, solvers use depth-first search with backtracking. The algorithm:

1. Selects an unassigned variable.
2. Picks a value from its current domain.
3. Recursively attempts to complete the assignment.
4. If a dead-end (empty domain) is reached, it backtracks to the last decision point and tries a different value. This is a complete algorithm—it will find a solution if one exists or prove none exists. It is enhanced by look-ahead strategies like Forward Checking.

Constraints are classified by the number of variables they involve, which dictates the propagation algorithm's complexity:

• Unary Constraints: Restrict a single variable (e.g., A ≠ 0). Handled by simple domain filtering.
• Binary Constraints: Relate two variables (e.g., A < B). Solvable by arc consistency algorithms.
• Global Constraints: Involve an arbitrary number of variables and use specialized, efficient propagation algorithms. The classic example is AllDifferent(x1, x2, ..., xn), which enforces that all variables in the set take distinct values.

A pure CSP is a feasibility problem—the goal is to find any complete assignment satisfying all constraints, or to prove none exists. This contrasts with optimization problems like Mixed-Integer Linear Programming (MILP). To handle optimization, CSPs are extended into Constraint Optimization Problems (COPs) by adding an objective function to minimize or maximize. The solver then uses a branch-and-bound technique, adding a constraint that each new solution must be better than the best found so far.

A declarative programming paradigm where relations between variables are stated as constraints, and a general-purpose solver finds feasible solutions. Unlike imperative programming, you define what must hold true, not how to compute it.

• Separates model (variables, domains, constraints) from search (propagation, branching)
• Uses constraint propagation to prune the search space before and during search
• Global constraints like alldifferent capture common combinatorial patterns efficiently
• Widely used in scheduling, routing, and configuration problems

A fundamental depth-first search algorithm for solving CSPs that incrementally builds candidate solutions and abandons a partial assignment as soon as it determines it cannot be completed.

• Assigns a value to a variable, then recursively attempts to assign the next
• Chronological backtracking: upon failure, returns to the most recently assigned variable
• Backjumping: an intelligent variant that skips irrelevant intermediate variables and jumps directly to the source of conflict
• Forms the backbone of most practical CSP solvers

A constraint propagation algorithm that enforces local consistency by removing values from variable domains that cannot participate in any solution to a binary constraint.

• An arc (X, Y) is consistent if for every value in X's domain, there exists some value in Y's domain that satisfies the binary constraint
• AC-3 iteratively revises arcs until no further domain reductions occur
• Does not guarantee global consistency but dramatically prunes the search space
• Higher levels: Path Consistency, k-Consistency generalize to larger variable subsets

Programs that determine the satisfiability of Boolean formulas in conjunctive normal form (CNF). Any finite-domain CSP can be encoded as a SAT instance.

• DPLL algorithm: systematic backtracking with unit propagation and pure literal elimination
• CDCL (Conflict-Driven Clause Learning): modern solvers learn new clauses from conflicts to prune future search
• Can handle problems with millions of variables and clauses
• Underpins hardware verification, planning, and software analysis tools

An optimization framework that minimizes a linear objective function subject to linear constraints, where some decision variables are restricted to integer values. CSPs with optimization criteria are often formulated as MILPs.

• Solved using Branch and Bound combined with cutting planes (Branch and Cut)
• Linear relaxation provides lower bounds that guide the search
• Commercial solvers like Gurobi and CPLEX solve industrial-scale problems
• Represents constraints like resource capacities, precedence relations, and logical conditions

Incomplete algorithms that start with a full but inconsistent assignment and iteratively repair constraint violations. They trade completeness for speed on large instances.

• Min-Conflicts heuristic: select a variable in conflict and assign it the value that minimizes new conflicts
• Highly effective for problems like N-Queens and scheduling where solutions are dense
• Tabu Search and Simulated Annealing escape local minima by occasionally accepting worse states
• Cannot prove unsatisfiability but often finds solutions rapidly in practice