ants (say, min and max). Other variants important for performance (say, ternary min and max) may be infeasible due to excessive programming and maintenance effort. Decomposing, on the other hand, massively increases memory consumption and runtime.

This paper introduces a third approach: *deriving* propagators from already existing propagators using *views*. This approach combines the efficiency of dedicated propagator implementations with the simplicity and effortlessness of decomposition.

Example 1 (Deriving a minimum propagator) Consider a propagator for the constraint max(x,y) = z. Given three additional propagators for x
′ = −x, y
′ = −y, and z
′ = −z, we could propagate the constraint min(x
′,y
′) = z
′ using the propagator for max(x,y) = z. Instead, this paper proposes to derive a propagator using views that perform the simple transformations corresponding to the three additional propagators.

Views transform input and output of a propagator. For example, a minus view on a variable x transforms the variable domain of x by negating each element, passes the transformed domain to the propagator, and performs the inverse transformation on the domain returned by the propagator. With views, the implementation of the maximum propagator can be reused: a propagator for the minimum constraint can be derived from a propagator for the maximum constraint and a minus view for each variable. ∗
This paper contributes an implementation-independentmodel for views and derived propagators, techniques for deriving propagators, concrete implementation techniques, and an evaluation that shows that views are widely applicable, drastically reduce programming effort, and yield an efficient implementation. More specifically, we identify the properties of views that are essential for deriving *perfect* propagators. The paper establishes a formal model that defines a view as a function and a derived propagator as functional composition of views (mapping values to values) with a propagator (mapping domains to domains). This model yields all the desired results: derived propagators are indeed propagators; they faithfully implement the intended constraints; domain consistency carries over to derived propagators; different forms of bounds consistency over integer variables carry over provided that the views satisfy additional yet natural properties.

We introduce techniques for deriving propagators that use views for transformation, generalization, specialization, and type conversion of propagators. We show how to apply these techniques for different variable domains using various views and how views can be used for the derivation of dual scheduling propagators.

We present and evaluate different implementation approaches for views and derived propagators. An implementation using parametric polymorphism (such as templates in C++) is shown to incur no or very low overhead. The architecture is orthogonal to the used constraint programming system and has been fully implemented in Gecode [10]. We analyze how successful the use of derived propagators has been for Gecode.

Plan of the paper. Section 2 introduces constraints and propagators. Section 3 establishes views and propagator derivation. Section 4 presents propagator derivation techniques. Section 5 describes an implementation architecture based on parametric propagators and range iterators. Section 6 discusses limitations of views. The implementation is evaluated in Section 7, and Section 8 concludes.

## 2 Preliminaries

This section introduces constraints, propagators, and propagation strength.