Constraint Programming

Constraint programming (CP) is a declarative paradigm for solving combinatorial problems that draws upon techniques from artificial intelligence, computer science, and operations research. Rather than specifying a sequence of computational steps, constraint programming focuses on describing the properties that a solution must satisfy. A solver is then responsible for finding values for decision variables that satisfy all stated constraints.
This paradigm is particularly effective for complex problems involving large search spaces, such as scheduling, planning, resource allocation, configuration, and optimisation tasks.
A central idea of constraint programming is the clear separation between problem modelling and problem solving, allowing users to express problems at a high level while relying on general-purpose solvers to explore solutions.

Declarative Modelling and Constraints

In constraint programming, a problem is defined by:

• A set of decision variables.
• A domain of possible values for each variable.
• A set of constraints restricting which combinations of values are allowed.

Constraints differ fundamentally from the control structures of imperative programming languages. They do not specify how to compute a result, but instead specify what conditions any valid solution must satisfy. For example, a constraint may state that two variables must have different values, or that a sum must not exceed a given bound.
In addition to constraints, users often specify or influence the search strategy, such as the order in which variables are considered or how values are selected. Standard solving techniques include chronological backtracking and constraint propagation, though many systems also support problem-specific heuristics to improve efficiency.

Constraint Logic Programming

Constraint programming has its theoretical roots in constraint logic programming (CLP), which embeds constraints within a logic programming framework. This approach was formalised in the 1980s by Joxan Jaffar and Jean-Louis Lassez, who extended earlier work on Prolog II by introducing general constraint-solving capabilities.
Early implementations of constraint logic programming include Prolog III, CLP(R) (constraints over the real numbers), and the CHIP programming language. CLP combines logical variables and backtracking with domain-specific solvers, enabling powerful declarative problem representations.
Although constraint programming originated in logic programming, it has since expanded well beyond it. Constraints can now be integrated with:

• Functional programming
• Imperative programming
• Term rewriting systems
• Object-oriented programming

Languages with built-in or strong support for constraints include Oz and Kaleidoscope, while many imperative languages rely on external constraint-solving libraries.

Constraint Satisfaction Problems

The formal foundation of constraint programming is the constraint satisfaction problem (CSP). A CSP is defined by:

• A finite set of variables.
• A domain of values for each variable.
• A set of constraints that restrict allowable combinations of variable values.

A constraint is a relation involving one or more variables that specifies which value combinations are permitted simultaneously. An assignment associates variables with values from their domains. Assignments may be partial, involving only some variables, or total, involving all variables.
A solution to a CSP is a total assignment that satisfies all constraints. Depending on the application, the goal may be to find:

• One solution.
• All possible solutions.
• Proof that no solution exists.

Types of Constraints

Constraints in constraint programming typically fall into several broad categories:

• Extensional constraints, defined by explicitly listing allowed or disallowed combinations of values.
• Arithmetic constraints, expressed using mathematical relations such as equality or inequality.
• Logical or global constraints, defined by higher-level semantics, such as AllDifferent or AtMost, which compactly encode common patterns.

Global constraints are especially important in practice, as they allow solvers to exploit specialised propagation algorithms.

Constraint Optimisation Problems

A constraint optimisation problem (COP) extends a CSP by associating it with an objective function to be minimised or maximised. In addition to satisfying all constraints, an optimal solution must achieve the best possible value of the objective.
In solving a COP, users may seek to:

• Find any feasible solution.
• Find the best solution.
• Prove the optimality of a solution.
• Prove that the problem is unsatisfiable.

Constraint optimisation is widely used in scheduling, logistics, and resource management.

Refinement and Perturbation Models

Constraint-based languages generally follow one of two conceptual models:

• Refinement model: Variables initially have broad domains, which are gradually reduced as constraints are applied and propagated until one or more consistent solutions emerge. This model is the most common and supports multiple solutions.
• Perturbation model: Variables have single values that are adjusted over time, with changes propagated to maintain consistency. Spreadsheet recalculation is a typical example.

While the perturbation model is often more intuitive for programmers, the refinement model is more expressive and central to constraint programming.

Domains of Constraint Programming

Constraint programming can be applied over a wide variety of domains, including:

• Boolean domains, as in Boolean satisfiability problems.
• Finite domains, which are among the most widely used and successful.
• Rational and real-number domains.
• Linear domains, with extensions to certain nonlinear constraints.
• Specialised domains for planning and scheduling.
• Mixed domains, combining multiple types.

In operations research, constraint programming is often identified specifically with finite-domain constraint programming.

Constraint Propagation

Constraint propagation is a key mechanism for reducing the search space of a CSP. It enforces local consistency conditions, such as node consistency, arc consistency, and path consistency, by removing values from variable domains that cannot participate in any valid solution.
Propagation does not change the set of solutions but simplifies the problem by pruning impossible values, making search more efficient. In some restricted cases, constraint propagation alone can detect unsatisfiability, though it is generally incomplete.

Constraint Solving Techniques

Three major algorithmic approaches are commonly used in constraint programming:

• Backtracking search, which incrementally assigns values to variables and backtracks upon encountering constraint violations.
• Local search, which iteratively improves candidate solutions by making local changes.
• Dynamic programming, applied in structured problems where overlapping subproblems can be exploited.