
## 4 Propagator Derivation Techniques

This section introduces techniques for deriving propagators using views. The techniques capture the transformation, generalization, specialization, and type conversion of propagators and are shown to be widely applicable across variable domains and application areas.

## 4.1 Transformation

Boolean connectives. For Boolean variables, where V = {0,1}, the only view apart from identity for Boolean variables captures negation. A *negation view* on x defines ϕx(v) = 1−v for x ∈ X and v ∈V. As already noted in Section 3.5, deriving propagators using Boolean views thus means to propagate using *literals* rather than variables.

The obvious application of negation views is to derive propagators for all Boolean connectives from just three propagators. A negation view for x in x = y yields a propagator for ¬x = y. From disjunction x∨y = z one can derive conjunction x∧y = z with negation views on x, y, z, and implication x → y = z with a negation view on x. From equivalence x ↔ y = z one can derive exclusive or x⊕y = z with a negation view on z.

As Boolean constraints are widespread, it pays off to optimize frequently occurring cases of propagators for Boolean connectives. One important propagator is for Wn i=1 xi = y with arbitrarily many variables. Again, conjunction can be derived with negation views on the xi and on y. Another important propagator implements the constraint Wn i=1 xi = 1. A dedicated propagator for this constraint is essential as the constraint occurs frequently and can be implemented efficiently using watched literals, see for example [12]. With views all implementation work is readily reused for conjunction. This shows a general advantage of views: effort put into optimizing a single propagator directly pays off for all other propagators derived from it.

Boolean cardinality. Like the constraint Wn i=1 xi = 1, the Boolean cardinality constraint ∑
n i=1 xi ≥ c occurs frequently and can be implemented efficiently using watched literals (requiring c + 1 watched literals, Boolean disjunction corresponds to the case where c = 1). But also a propagator for ∑
n i=1 xi ≤ c can be derived using negation views on the xi with the following transformation:

$$\begin{array}{r l r l r l}{\sum_{i=1}^{n}x_{i}\leq c}&{{}\iff\quad-\sum_{i=1}^{n}x_{i}\geq-c}&{{}\iff\quad n-\sum_{i=1}^{n}x_{i}\geq n-c}\\ {\iff\quad\sum_{i=1}^{n}1-x_{i}\geq n-c}&{{}\iff\quad\sum_{i=1}^{n}\neg x_{i}\geq n-c}\end{array}$$

Reification. Many reified constraints (such as (∑
n x=1 xi = c) ↔ b) also exist in a negated version (such as (∑
n x=1 xi 6= c) ↔ b). Deriving the negated version is trivial by using a negation view on the Boolean control variable b. This contrasts nicely with the effort without views: either the entire code must be duplicated or the parts that perform checking whether the constraint or its negation is subsumed must be factored out and combined differently for the two variants. Transformation using set views. Set constraints deal with variables whose values are finite sets. Using *complement views* (analogous to Boolean negation, as sets with their usual operations also form a Boolean algebra) on x,y,z with a propagator for x∩y = z yields a propagator for x∪y = z. A complement view on y yields x \ y = z.