

![0_image_0.png](0_image_0.png)

Transformation using integer views. The obvious integer equivalent to negation views for Boolean variables are *minus views:* a minus view on an integer variable x is defined as ϕx(v) = −v. Minus views help to derive propagators following simple transformations: for example, min(x,y) = z can be derived from max(x,y) = z by using minus views for x, y, and z.

Transformations through minus views can improve performance in subtle ways.

Consider a bounds(Z)-complete propagator for multiplication x × y = z (for example,
[1, Section 6.5] or [32]). Propagation depends on whether zero is still included in the domains of x, y, or z. Testing for inclusion of zero each time the propagator is executed is inefficient and leads to a convoluted implementation. Instead, one would like to rewrite the propagator to special variants where x, y, and z are either strictly positive or negative. These variants can propagate more efficiently, in particular because propagation can easily be made idempotent. Instead of implementing three different propagators (x,y,z strictly positive; only x or y strictly positive; only z strictly positive),
a single propagator assuming that all views are strictly positive is sufficient. The other propagators can be derived using minus views.

Again, with views it becomes realistic to optimize a single implementation of a propagator and derive other, equally optimized, implementations. The effort to implement all required specialized versions without views is typically unrealistic.

Scheduling propagators. An important application area is constraint-based scheduling, see for example [2]. Many propagation algorithms for constraint-based scheduling are based on tasks, where a task t is characterized by its start time, processing time
(how long does the task take to be executed on a resource), and end time. Scheduling algorithms are typically expressed in terms of earliest start time (est(t)), latest start time (lst(t)), earliest completion time (ect(t)), and latest completion time (lct(t)).

Another particular aspect of scheduling algorithms is that they are often required in two, mutually dual, variants. Let us consider not-first/not-last propagation as an example. Assume a set of tasks T and a task t 6∈T to be scheduled on the same resource. Then t cannot be scheduled before the tasks in T (t is not-first in T ∪ {t}), if ect(t) >
lst(T) (where lst(T) is a conservative estimate of the latest start time of all tasks in T). Hence, est(t) can be adjusted to leave some room for at least one task from T. The dual variant is that t is not-last: if ect(T) > lst(t) (again, ect(T) estimates the earliest completion time of T), then lct(t) can be adjusted.

Running the dual variant of a scheduling algorithm on tasks t ∈ T is the same as running the original algorithm on the *dual tasks t*′ ∈ T
′, which are simply mirrored at the 0-origin of the time scale (see Figure 1):
est(t
′) = −lct(t) ect(t
′) = −lst(t) lst(t
′) = −ect(t) lct(t
′) = −est(t)
The dual variant of a scheduling propagator can be automatically derived using a minus view that transforms the time values. In our example, only a propagator for not-first