Skip to content
Back to search results

Constraint Programming

Introduced by
Rossi, van Beek & Walsh
Year
2006
Type
Declarative combinatorial optimization
Family
Mathematical programming
Font size

What does it do?

Constraint Programming (CP) is a declarative optimization paradigm in which a problem is formulated as a set of variables, finite domains, and constraints, and a solver systematically searches for assignments that satisfy all constraints.

Formalized comprehensively by Rossi, van Beek, and Walsh in their 2006 Handbook of Constraint Programming, CP unifies propagation-based pruning with intelligent backtracking search to tackle combinatorial problems across scheduling, planning, and configuration domains.

The intuition behind the method

Think of CP as filling in a complex puzzle: each cell is a variable with a set of legal values, and every rule of the puzzle is a constraint. Rather than guessing blindly, CP uses the rules to immediately eliminate impossible values from neighboring cells whenever one cell is filled in. This propagation shrinks the search space dramatically, so the solver explores only plausible combinations — backtracking and revising only when it reaches a dead end.

History

Constraint Programming emerged from artificial intelligence research in the 1970s with early work on constraint satisfaction by Montanari and Mackworth. It matured through the 1980s and 1990s with the development of arc consistency algorithms, global constraints, and practical solvers such as CHIP and ILOG Solver. The field was authoritatively consolidated by Rossi, van Beek, and Walsh in the 2006 Handbook of Constraint Programming, which remains the definitive reference, covering theory, algorithms, and applications across combinatorial optimization.

When to use it

Constraint Programming is best suited for combinatorial problems with complex, heterogeneous constraints — scheduling, timetabling, configuration, and routing — where feasibility is as important as optimality. It assumes problems can be modeled with discrete or enumerable variable domains. CP is less effective for continuous optimization or large-scale linear programs, where Linear Programming or Mixed-Integer Programming solvers typically dominate. When constraints are highly structured and propagation can prune large portions of the search space, CP outperforms general-purpose metaheuristics.

Limitations and considerations

  • Scalability: worst-case exponential search makes CP slow on very large instances with weak propagation.
  • Requires good modeling: poor variable/value ordering heuristics or missing global constraints lead to unnecessarily large search trees.
  • Continuous domains: CP is natively designed for discrete domains; continuous problems require specialized extensions or hybrid approaches.
  • Solver expertise: effective use demands familiarity with constraint modeling techniques and solver-specific global constraint libraries.

Source conditions do not replace independent scientific review or validation by an analysis engine.

Strengths

  • Declarative modeling: complex real-world rules are expressed directly as constraints without specifying the search procedure.
  • Powerful pruning: constraint propagation eliminates infeasible regions early, often reducing search by orders of magnitude.
  • Handles heterogeneous constraints: logical, arithmetic, global, and user-defined constraints coexist naturally in a single model.
  • Guarantees completeness: the solver either finds an optimal solution or proves infeasibility, unlike heuristic methods.

Applications

  • Employee and nurse scheduling: assigning staff to shifts while satisfying availability, labor law, and skill constraints.
  • Timetabling: constructing university or school timetables subject to room capacity, instructor availability, and curriculum constraints.
  • Configuration: assembling product configurations (computers, vehicles) from component catalogs under compatibility and resource constraints.
  • Vehicle routing and logistics: planning delivery routes subject to time windows, vehicle capacities, and driver regulations.
  • Combinatorial auctions and resource allocation: assigning resources to bidders or tasks under exclusivity and budget constraints.

How it works

How it works

1

The problem is encoded as a Constraint Satisfaction Problem triple consisting of variables X, their finite domains D, and a set of constraints C. Each variable x_i can be assigned any value from its domain D_i. Constraints define permissible combinations of values across subsets of variables, translating real-world rules — capacity limits, precedence relations, resource conflicts — into a mathematical structure the solver can reason over.

Formula
\text{CSP} = \langle X, D, C \rangle \quad X = \{x_1, x_2, \ldots, x_n\},\; D = \{D_1, D_2, \ldots, D_n\}
2

Before and during search, the solver applies arc consistency and other local-consistency algorithms to prune domain values that cannot participate in any valid solution. For every pair of constrained variables, arc consistency removes values from one variable's domain for which no supporting value exists in the other's domain. This propagation is triggered repeatedly after each assignment, drastically reducing the effective search space.

Formula
\text{AC}(x_i, x_j): \forall a \in D_i,\; \exists b \in D_j \text{ s.t. } c_{ij}(a, b) \text{ holds}
3

The solver selects an unassigned variable — typically using heuristics such as minimum remaining values or degree — and tentatively assigns it a value from its pruned domain. Propagation runs again; if a contradiction is detected (an empty domain), the solver backtracks to the most recent choice point and tries an alternative value. Backjumping and nogood recording can further accelerate recovery from failures.

Formula
x_i \leftarrow a_i \in D_i,\quad \text{propagate},\quad \text{if fail: backtrack and reassign}
4

When all variables have been assigned values consistent with every constraint, the complete assignment S* constitutes a solution. For optimization problems, an objective function guides search toward the best feasible solution, and branch-and-bound strategies progressively tighten the bound as better solutions are found, until the global optimum is certified or a time limit is reached.

Formula
S^* = \{(x_1, a_1^*), \ldots, (x_n, a_n^*)\} : \forall c \in C,\; c(a_1^*, \ldots, a_n^*) = \text{true}

Common pitfalls

  • Over-constraining the model with redundant or conflicting constraints causes the solver to report infeasibility incorrectly.
  • Neglecting global constraints (e.g., alldifferent, cumulative) misses propagation opportunities that specialized algorithms provide for free.
  • Ignoring search heuristics and relying on default variable/value ordering can waste exponential time on pathological orderings.
  • Confusing constraint satisfaction with optimization: forgetting to add an objective function and bound-tightening yields only the first feasible solution, not the best one.

Frequently asked questions

How does Constraint Programming differ from Integer Linear Programming?

While both solve combinatorial problems, ILP requires all constraints and objectives to be linear, enabling efficient LP-relaxation bounds. CP imposes no such linearity requirement and instead relies on constraint propagation and systematic search. CP handles complex logical and global constraints more naturally, whereas ILP often scales better on problems with strong linear structure and large variable counts.

What are global constraints and why do they matter?

Global constraints are high-level constraints over arbitrary numbers of variables — for example, alldifferent (all variables take distinct values) or cumulative (resource usage at any time does not exceed capacity). They matter because solvers implement dedicated, highly efficient propagation algorithms for each, achieving far stronger pruning than decomposing the same condition into many binary constraints, which would leave much of the search space unexplored.

Can Constraint Programming find optimal solutions, or only feasible ones?

CP can find optimal solutions by combining feasibility search with an objective function. The solver uses branch-and-bound: once a feasible solution is found, it adds a constraint requiring any subsequent solution to be strictly better, continuing until no improvement is possible. This certifies optimality. If runtime is limited, the best solution found so far is returned as an approximation.

Related methods

Sources

  1. Rossi, F., van Beek, P., & Walsh, T. (Eds.). (2006). Handbook of Constraint Programming. Elsevier.

    ISBN: 978-0-444-52726-4
    Copied.