2.4 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; interval propagation only narrows the bounds of a domain.

Consider a propagator for the constraint

{2\cdot X}=Y

over a constraint store

X\in1\#10
\qquad
Y\in1\#7

Under domain propagation, the propagator can narrow the domains to

X\in1\#3
\qquad
Y\in\{2,4,6\}

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

X\in1\#3
\qquad
Y\in2\#6

In practice, interval propagation is usually preferable over domain propagation because of its lower computational costs. We will see later that Oz offers for some constraints two propagators, one for interval and one for domain propagation.


Christian Schulte and Gert Smolka
Version 1.4.0 (20080702)