The Constraint Programming Paradigm

Introduces constraint programming (CP) as a declarative paradigm for combinatorial problems. Covers the three components of a CP model (variables, finite domains, constraints), constraint propagation for domain reduction, and global constraints such as alldifferent.

Step 1 of 157%

Tutorial

The Constraint Programming Paradigm

The constraint programming (CP) paradigm is a declarative approach to combinatorial problems. We describe what conditions a solution must satisfy, rather than how to find it.

A CP model consists of three components:

Decision variables $x_1, x_2, \ldots, x_n.$
A finite domain $D(x_i)$ for each variable — the set of values it may take.
A set of constraints — arbitrary relations over the variables that solutions must satisfy.

For example, the problem "choose integers $x$ and $y$ between $1$ and $4$ such that $x+y=5$ and $x \neq y$ " becomes:

Variables: $x, y$
Domains: $D(x) = D(y) = \{1, 2, 3, 4\}$
Constraints: $x + y = 5, \quad x \neq y$

Unlike in integer programming, CP constraints are not restricted to linear (in)equalities. They may include $\neq$ , logical implications, table lookups, and structured global relations stated directly.