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:

$\mathcal{B}\quad{:}{:}{=}\quad 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.

Weakening
$I\in D$	$\rightarrow$	$I\in D'$	where $D'\supseteq D$
$D\subseteq S$	$\rightarrow$	$D'\subseteq S$	where $D'\subseteq D$
$S\subseteq D$	$\rightarrow$	$S\subseteq D'$	where $D'\supseteq D$
Strengthening
$I\in D_1\wedge I\in D_2$	$\rightarrow$	$I\in D_1\cap D_2$
$D_1\subseteq S\wedge D_2\subseteq S$	$\rightarrow$	$D_1\cup D_2\subseteq S$
$S\subseteq D_1\wedge S\subseteq D_2$	$\rightarrow$	$S\subseteq D_1\cap D_2$
Contradiction
$I\in\emptyset$	$\rightarrow$	$\textbf{false}$
$D_1\subseteq S\wedge S\subseteq D_2$	$\rightarrow$	$\textbf{false}$	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 , this is the smallest such that $I\in D$ . For a set variable 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 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.