# Range And **Roots**:

Two Common Patterns for Specifying and Propagating Counting and Occurrence Constraints∗
Christian Bessiere LIRMM, CNRS and U. Montpellier Montpellier, France bessiere@lirmm.fr Emmanuel Hebrard 4C and UCC
Cork, Ireland e.hebrard@4c.ucc.ie Brahim Hnich Izmir University of Economics Izmir, Turkey brahim.hnich@ieu.edu.tr Zeynep Kiziltan Department of Computer Science Univ. di Bologna, Italy zeynep@cs.unibo.it Toby Walsh NICTA and UNSW
Sydney, Australia tw@cse.unsw.edu.au Keywords: Constraint programming, constraint satisfaction, global constraints, open global constraints, decompositions

## Abstract

We propose Range and Roots which are two common patterns useful for specifying a wide range of counting and occurrence constraints. **We design specialised**
propagation algorithms for these two patterns. Counting and occurrence constraints specified using these patterns thus directly inherit a propagation algorithm. To illustrate the capabilities of the Range and Roots **constraints, we specify a number of**
global constraints taken from the literature. Preliminary **experiments demonstrate**
that propagating counting and occurrence constraints using these two patterns leads to a small loss in performance when compared to specialised global constraints and is competitive with alternative decompositions using elementary constraints.

∗This paper is a compilation and an extension of [10], [11], and [12]. The first author was supported by the ANR project ANR-06-BLAN-0383-02.

1