# View-Based Propagator Derivation

Christian Schulte ICT, KTH - Royal Institute of Technology, Sweden, **cschulte@kth.se**
Guido Tack Programming Systems Lab, Saarland University, Germany, **tack@ps.uni-sb.de**

## Abstract 1

When implementing a propagator for a constraint, one must decide about variants: When implementing min, should one also implement max? Should one implement linear constraints both with unit and non-unit coefficients? Constraint variants are ubiquitous: implementing them requires considerable (if not prohibitive) effort and decreases maintainability, but will deliver better performance than resorting to constraint decomposition.

This paper shows how to use views 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 type conversion are developed. The paper introduces an implementation architecture for views that is independent of the underlying constraint programming system. A detailed evaluation of views implemented in Gecode shows that derived propagators are efficient and that views often incur no overhead. Without views, Gecode would either require 180000 rather than 40000 lines of propagator code, or would lack many efficient propagator variants. Compared to 8000 lines of code for views, the reduction in code for propagators yields a 1750% return on investment.

## 1 Introduction

When implementing a propagator for a constraint, one typically must also decide whether to implement some of its variants. When implementing a propagator for the constraint max{x1,...,xn} = y, should one also implement min{x1,...,xn} = y? The latter can be implemented using the former as max{−x1,...,−xn} = −y. When implementing a propagator for the linear equation ∑
n i=1 aixi = k for integer variables xi and integers ai and k, should one also implement the special case ∑
n i=1 xi = k for better performance? When implementing a propagator for the reified linear equation
(∑
n i=1 xi = c) ↔ b, should one also implement (∑
n i=1 xi 6= c) ↔ b? These two constraints only differ by the sign of b, as the latter is equivalent to (∑
n i=1 xi = c) ↔ ¬b.

The two straightforward approaches for implementing constraint variants are to either implement dedicated propagators for the variants, or to decompose. In the last example, for instance, the reified constraint could be decomposed into two propagators, one for (∑
n i=1 xi = c) ↔ b
′, and one for b ↔ ¬b
′, introducing an additional variable b
′.

Implementing the variants inflates code and documentation and is error prone.

Given the potential code explosion, one may be able to only implement some variarXiv:0908.2050v1 [cs.AI] 14 Aug 2009