COMPUTATIONAL OPTIMIZATION
Constraint programming is a declarative method for solving problems by stating variables, their possible values, and restrictions on combinations of values. A solver then searches for assignments satisfying those constraints, or optimizes an objective over the feasible assignments. The approach is especially effective when relationships are more naturally expressed as rules than as algebraic formulas, including scheduling, configuration, routing, rostering, and puzzle solving.1
Constraint programming represents a problem as a constraint satisfaction problem (CSP): a set of variables, a domain for each variable, and constraints that rule out inconsistent combinations. A solution assigns every variable a value from its domain while satisfying all constraints; an optimization model additionally ranks solutions using an objective function. For example, a timetable may use variables for courses, rooms, and periods, with constraints forbidding clashes and limiting room capacity.
Constraints can be unary, binary, or global. A unary constraint restricts one variable, while a binary constraint relates two variables. Global constraints express recurring structures such as all-different, cumulative resource use, or ordered sequences; specialized propagation algorithms can exploit their structure more effectively than a collection of simple pairwise rules.1 Domains may contain integers, Boolean values, sets, finite enumerations, or intervals.
Constraint solvers alternate between propagation and search. Propagation removes domain values that cannot participate in any complete solution, often without selecting a final value. When propagation cannot decide the problem, a search procedure branches on a variable or constraint, propagates the consequences, and backtracks when a branch becomes inconsistent.
Heuristics determine which variable and value to branch on, while consistency notions such as arc consistency describe how aggressively relationships are filtered. Modern systems commonly combine finite-domain propagation with SAT solving, mixed-integer techniques, lazy clause generation, or linear relaxation. Google OR-Tools CP-SAT, for example, combines constraint-programming ideas with Boolean reasoning and integer optimization rather than treating these paradigms as isolated alternatives.3 The resulting performance depends heavily on modeling choices, symmetry breaking, implied constraints, and good bounds on variables.
Constraint programming is usually written in a high-level modeling language or through a solver library, allowing the model to emphasize what must hold rather than the sequence of computational steps. MiniZinc is a widely used solver-independent modeling language that can compile one model for different back ends, including constraint, SAT, and mixed-integer solvers.2
Applications include airline and school scheduling, workforce rostering, vehicle routing, production planning, telecommunications, software configuration, and electronic design. Constraint methods are also useful in interactive settings because a user can add or retract requirements and ask whether the revised model remains feasible. In practice, they are often combined with domain-specific heuristics, simulation, or mathematical programming: constraint programming handles combinatorial structure, while other methods address large numerical subproblems or uncertainty.
Constraint programming grew from several traditions rather than one single invention. Its modern form draws on artificial intelligence search, logic programming, relational databases, and operations research; the constraint logic programming tradition made constraints part of programming-language execution, while finite-domain solvers brought strong propagation to discrete problems.
A subtle strength is that infeasibility can be diagnosed structurally. Some systems identify an unsatisfiable core, a small collection of requirements that cannot coexist, which helps planners revise policies instead of merely receiving “no solution.” Symmetry is another overlooked issue: interchangeable workers, rooms, or machines can create many equivalent search branches, so symmetry-breaking constraints may reduce computation dramatically. Constraint models can also represent reification, in which a Boolean variable records whether another constraint holds, enabling conditional rules and explanations.
The field has a substantial research and professional community organized through the Association of Constraint Programming and its annual international conference series.4
Terminology varies across subfields: “constraint programming” may refer narrowly to finite-domain propagation and search, or broadly to declarative solving systems that combine constraint reasoning with SAT, integer programming, and local search.
Help improve the encyclopedia. Reports go straight to the site manager.