2.2.1 Basic Constraints

This intuitive way, presented above, of capturing partial information about an assignment can be formally presented as a logical system of Basic Constraints. Its abstract syntax is given by:

I\in D\ \mid\ D\subseteq S\ \mid\ S\subseteq D\ \mid\
\textbf{false}\ \mid\ \mathcal{B}_1\wedge\mathcal{B}_2

It is equipped with the following inference rules.


I\in D


I\in D'


where D'\supseteq D

D\subseteq S


D'\subseteq S


where D'\subseteq D

S\subseteq D


S\subseteq D'


where D'\supseteq D


I\in D_1\wedge I\in D_2


I\in D_1\cap D_2



D_1\subseteq S\wedge D_2\subseteq S


D_1\cup D_2\subseteq S



S\subseteq D_1\wedge S\subseteq D_2


S\subseteq D_1\cap D_2









D_1\subseteq S\wedge S\subseteq D_2




where D_1\not\subseteq D_2

Of course, after saturation with the above rules, for each variable there is always a most specific approximation of its assignment. For an integer variable I, this is the smallest D such that I\in D. For a set variable S there is a largest lower bound D_1\subseteq S and a smallest upper bound S\subseteq D_2. In practice, these most specific basic constraints are the only ones that the system needs to represent (all others can be derived by weakening).

Constraint Store

A constraint programming system contains a constraint store which is the (saturated) set of basic constraints representing the partial information currently known about the assignment.

Determined Variables

We say that a variable is determined when its assignment has been decided. For an integer variable I\in D this happens when its domain D becomes a singleton. For a set variable D_1\subseteq S\subseteq D_2 this happens when its lower bound becomes equal to its upper bound.

Denys Duchier
Version 1.2.0 (20010221)