5.1 Some Facts About Propagators

domain propagation, interval propagation

If a propagator is invoked, it tries to narrow the domains of the variables it is posted on. The amount of narrowing of domains depends on the operational semantics of the propagator. There are two main schemes for the operational semantics of a propagator. Domain propagation means that the propagator narrows the domains such that all values are discarded, which are not contained in a solution of the modeled constraint. But due to efficiency reasons, most propagators provide only interval propagation, i. e. only the bounds of domains are narrowed. For some propagators, there is an operational semantics in between both schemes.

A propagator ceases to exist at least if all the variables it is posted on are determined. In the following sections, only exceptions from this rule are mentioned, i. e. if the propagator ceases to exist earlier. For example, {=<: Y} ceases to exist if the current upper bound of X is smaller than or equal to the current lower bound of Y.


Denys Duchier, Leif Kornstaedt, Martin Homik, Tobias Müller, Christian Schulte and Peter Van Roy
Version 1.4.0 (20080702)