# Perfect Derived Propagators

Christian Schulte1 **and Guido Tack**2 1
**ICT, KTH - Royal Institute of Technology, Sweden,** cschulte@kth.se 2 **PS Lab, Saarland University, Saarbr¨ucken, Germany,** tack@ps.uni-sb.de Abstract. **When implementing a propagator for a constraint, one must**
decide about variants: When implementing min, should one also implement max? Should one implement linear equations both with and without coefficients? Constraint variants are ubiquitous: implementing them requires considerable (if not prohibitive) effort and decreases maintainability, but will deliver better performance.

This paper shows how to use variable views, previously introduced for an implementation architecture, to derive *perfect* **propagator variants. A**
model for views and derived propagators is introduced. Derived propagators are proved to be indeed perfect in that they inherit essential properties such as correctness and domain and bounds consistency. **Techniques** for systematically deriving propagators such as transformation, generalization, specialization, and channeling are developed for several variable domains. We evaluate the massive impact of derived propagators.

Without derived propagators, Gecode would require 140 000 rather than 40 000 lines of code for propagators.

## 1 Introduction

When implementing a propagator for a constraint, one typically needs to decide whether to also implement some of its variants. For example, when implementing a propagator for maxn i=1 xi = y**, should one also implement min**n i=1 xi = y**? When**
implementing the linear equation Pn i=1 aixi = c for integer variables xi and integers ai and c**, should one also implement** Pn i=1 xi = c **for better performance?**
When implementing the reified linear equation (Pn i=1 xi = c) ⇔ b**, should one**
also implement its almost identical algebraic variant (Pn i=1 xi 6= c) ⇔ b?

Implementing inflates code and documentation. Not implementing increases space and runtime: by using more general propagators or by decomposing into several other constraints. Worse, given the potential code explosion, one may be able to only implement some variants (say, minimum and maximum). Other variants important for performance (say, minimum and maximum for two **variables)**
may be infeasible due to excessive programming and maintenance effort.

Here, we follow a third approach: we derive propagators from already existing propagators using variable views. In [12], we introduced an implementation architecture for variable views to reuse generic propagators without performance penalty. This architecture has been implemented in Gecode [5], and is in **fact** essential for the system, as it saves approximately 100 000 lines of code. Due to arXiv:0806.1806v1 [cs.AI] 11 Jun 2008