Interval and Domain Propagation

There are two established schemes for the operational semantics of a propagator. Domain propagation narrows the domains of the variables as much as possible, i.e. all values that are not consistent with the constraint are removed; interval propagation only narrows the bounds of a domain.

Consider a propagator for the constraint

2 ^. X = Y

over a constraint store

$X \in \ensuremath{\{1,\dots,10\}} \hspace{4mm} Y \in \ensuremath{\{1,\dots,7\}}$

Under domain propagation, the propagator can narrow the domains to

$X \in \ensuremath{\{1,\dots,3\}} \hspace{4mm} Y \in \{2,4,6\}$

Under interval propagation, the propagator can narrow only the domain bounds, which yields

$X \in \ensuremath{\{1,\dots,3\}} \hspace{4mm} Y \in \ensuremath{\{2,\dots,6\}}$

In practice, interval propagation is usually preferable over domain propagation because of its lower computational costs. But domain propagation often leads to considerably smaller search trees (figure 2). In Alice, some propagators have an additional argument conlevel. There you can specify the propagators consistency level.