# 1. Preface

*“Although dictionaries give the impression of analyzing words all the way down to their very atoms, all they do in fact is graze their surfaces.”*

– Douglas Hofstadter, Emmanuel Sander, *Surfaces and Essences*

This catalogue presents a list of global constraints.
Within this catalogue the term *global constraint* should be
understood as an *expressive and concise condition involving
a non-fixed number of variables*. This informal definition
does not make any assumption neither about the potential use of a global
constraint nor about the techniquesAs quoted by J. N. Hooker
in [Hooker07], “*identifying a field with its techniques is an intellectually
as well as practically unsatisfying*” and has a lot of drawbacks. associated with the
development of global constraints.
It contains about 423 constraints, which are explicitly described in terms of
graph properties and/or
automata and/or
first order logic formulae and/or
conjunction of other constraints.

This *Global Constraint Catalogue* is an expanded version of the
list of global constraints presented
in [BeldiceanuR00] and an updated version
of [BeldiceanuCarlssonRampon05].
The principle used for describing global constraints has been
slightly modified in order to deal with a larger number of
global constraints. Since 2003, we try to provide an
automaton that recognises the solutions associated with a global constraint.
Since 2009, we also try to provide a first order logic formula for defining
the solutions accepted by a geometrical constraint.

Writing a dictionary is a long process, especially in a field where new words are defined every year. In this context, one difficulty is to express explicitly the meaning of global constraints in terms of meta-data. Finding an appropriate and concise description that both easily captures the meaning of most global constraints and allows fast inferencesE.g., in the context of the constraint and model seeker [BeldiceanuSimonis11], [BeldiceanuSimonis12] we have gradually identified a number of properties for inferring that a constraint/conjunction of constraints is implied by another constraint/conjunction of constraints. involving global constraints seems to be a tricky task.

One may wonder how so many constraints can be used at all in practice?
However many fields produce a number of articles containing partial and
specific results. Within the area of global constraints, we fill that trying extracting
and classifying such knowledge, as well as providing meta-data for
encoding it, may be a help, both for humans and machines, to exploit systematically
ongoing research results and to put these results in perspective. Work about the
*constraint seeker* [BeldiceanuSimonis11] and the
*model seeker* [BeldiceanuSimonis12]
relies on these meta-data to identify global constraints and to automatically
come up with a constraint model from a set of positive samples.

#### Goal of the catalogue.

This catalogue has four main goals. First, it provides an overview of most of the different global constraints that were gradually introduced in the area of constraint programming since the work of J.-L. Laurière on ALICE [Lauriere78]. It also identifies new global constraints for which no existing published work exists. The global constraints are arranged in alphabetic order, and for all of them a description and an example are systematically provided. When available, it also presents some typical usage as well as some pointers to existing filtering algorithms.

Second, the global constraints described in this catalogue are not
only accessible to humans, who can read the catalogue for searching
for some information. It is also available to machines, which can
read and interpret it. This is why there exists an electronic
version of this catalogue where one can get, for most global
constraints, a complete description in terms of meta-data.
In fact, most of this catalogue and its figures were automatically
generated from this electronic version by a computer program.
This description is based on three complementary ways to look at
a global constraint. The first one defines a global constraint
as searching for a graph with specific
properties [Beldiceanu00],
the second one characterises a global constraint in terms
of an automaton that only recognises the solutions associated
with that global
constraint [BeldiceanuCarlssonPetit04], [Pesant04]Automata
were first used in the 90ies by N. R. Vempaty [Vempaty92] and
J. Amilhastre [Amilhastre99] in the context of constraint
networks. Later on in 2007, they were also used by
M.-C. Coté *et al.* [CoteGendronRousseau07]
in the context of linear programming.,
while the third one defines in the context of geometric constraints
a global constraint as a restricted first order
logic formula [CarlssonBeldiceanuMartin08].
The key point of these descriptions is their ability to define
explicitly in a concise way the meaning of most global constraints.
In addition these descriptions can also be systematically turned
into polynomial filtering algorithms.

Third, we hope that this unified description of apparently diverse global constraints will allow for establishing a systematic link between the properties of basic concepts used for describing global constraints and the properties of the global constraints as a whole.

Finally, we also hope that it will attract more people from the algorithmic
community into the area of constraints. To a certain extent this has already started
at places like CWI in Amsterdam, the Max-Planck für Informatik (Saarbrücken)
or the university of Waterloo.
We also hope that it will attract people from combinatorics in order to produce
theories and knowledge that could nicely unify and/or put in perspective different
aspects of constraints (i.e., breaking symmetries, counting the number of solutions).
Identifying bijections [Stanley11], [Stanley01] relating global constraints to well known
combinatorial objects would be a step in this direction.This is currently the
case only for a few constraints like $\mathrm{\U0001d68a\U0001d695\U0001d695\U0001d68d\U0001d692\U0001d68f\U0001d68f\U0001d68e\U0001d69b\U0001d68e\U0001d697\U0001d69d}$,
$\mathrm{\U0001d68c\U0001d6a2\U0001d68c\U0001d695\U0001d68e}$ or $\mathrm{\U0001d69d\U0001d69b\U0001d68e\U0001d68e}$.
The information about the number of solutions of a global constraint in the **Counting**
slot could certainly help identifying relevant combinatorial objects.

#### Use of the catalogue.

The catalogue is organised into five chapters:

Chapter 1 provide a short overview of the main entries you may first consult when you are not familiar with the catalogue.

Chapter 2 explains how the meaning of global constraints is described in terms of graph-properties or in terms of automata. On the one hand, if one wants to consult the catalogue for getting the informal definition of a global constraint, examples of use of that constraint or pointers to filtering algorithms, then one only needs to read the first section of Chapter 2: describing the arguments of a global constraint, page 2.2. On the other hand, if one wants to understand those entries describing explicitly the meaning of a constraint then all the material of Chapter 2 is required.

Chapter 3 describes the content of the catalogue as well as different ways for searching through the catalogue. This material is essential.

Chapter 4 covers additional topics, such as the differences from the 2000 report [BeldiceanuR00] on global constraints, the generation of implied constraints that are systematically linked to the graph-based description of a global constraint, and the electronic version of the catalogue. The material describing the format of the entries of a global constraint is mandatory for those who want to exploit the electronic version in order to write pre-processors for performing various tasks for a global constraint.

Finally, Chapter 5 corresponds to the catalogue itself, which gives the global constraints in alphabetical order.

#### Acknowledgments.

Nicolas Beldiceanu was the principal investigator and main architect of the constraint catalogue, provided the main ideas, and wrote a checker for the constraint descriptions, a figure generation program for the constraint descriptions and an evaluator for most constraints. Jean-Xavier Rampon provided the proofs for the graph invariants. Mats Carlsson contributed to the design of the meta-data format, generated some of the automata together with their negated forms, provide some constraints evaluators, and wrote the program that created the LaTeX version of this catalogue from the constraint descriptions.

The idea of describing explicitly the meaning of global constraints in a declarative way has been inspired by the work on meta-knowledge of Jacques Pitrat [Pitrat01], [Pitrat08], [Pitrat09].

We are grateful to Magnus Ågren, Abderrahmane Aggoun, Ernst Althaus, María Andreína Francisco Rodríguez, Gregor Baues, Christian Bessière, Éric Bourreau, Sebastian Brand, Pascal Brisset, Hadrien Cambazard, Gilles Chabert, Peter Chan, Philippe Charlier, François Clautiaux, Evelyne Contejean, Radoslaw Cymer, Romuald Debruyne, Frédéric Deces, Sophie Demassey, Mehmet Dincbas, Grégoire Dooms, François Fages, Jean-Guillaume Fages, Pierre Flener, Xavier Gandibleux, Yan Georget, Dávid Hanák, Emmanuel Hebrard, Pascal Van Hentenryck, Fabien Hermenier, Han J. A. Hoogeveen, Stefan Hougardy, Giuseppe F. Italiano, Antoine Jouglet, Narendra Jussien, Irit Katriel, Waldemar Kocjan, Per Kreuger, Krzysztof Kuchcinski, Mikael Zayenz Lagerkvist, Michel Leconte, Christophe Lecoutre, Arnaud Letort, Xavier Lorca, Michael J. Maher, Michael Marte, Julien Martin, Julien Menana, Per Mildner, Nicolas Museux, Justin Pearson, Gilles Pesant, Thierry Petit, Emmanuel Poder, Charles Prud'homme, Luis Quesada, Claude Guy Quimper, Jean-Charles Régin, Florian Richoux, Guillaume Rochart, Xavier Savalle, Pierre Schaus, Thomas Schiex, Christian Schulte, Helmut Simonis, Péter Szeredi, Radoslaw Szymanek, Guido Tack, Sven Thiel, Charlotte Truchet, Eliane Vacheret, Willem-Jan van Hoeve, Richard J. Wallace, Toby Walsh and Stéphane Zampelli for correction, discussion, information exchange or common work about specific global constraints.

Furthermore, we are grateful
to Irit Katriel who contributed by updating the description of some filtering algorithms related to flow
and matching of the catalogue,
to Luis Quesada and Stéphane Zampelli
who provide inputs for the $\mathrm{\U0001d68d\U0001d698\U0001d696}\_\mathrm{\U0001d69b\U0001d68e\U0001d68a\U0001d68c\U0001d691\U0001d68a\U0001d68b\U0001d692\U0001d695\U0001d692\U0001d69d\U0001d6a2}$,
the $\mathrm{\U0001d69c\U0001d69e\U0001d68b\U0001d690\U0001d69b\U0001d68a\U0001d699\U0001d691}\_\mathrm{\U0001d692\U0001d69c\U0001d698\U0001d696\U0001d698\U0001d69b\U0001d699\U0001d691\U0001d692\U0001d69c\U0001d696}$
and $\mathrm{\U0001d690\U0001d69b\U0001d68a\U0001d699\U0001d691}\_\mathrm{\U0001d692\U0001d69c\U0001d698\U0001d696\U0001d698\U0001d69b\U0001d699\U0001d691\U0001d692\U0001d69c\U0001d696}$ constraints,
and to Radoslaw Szymanek and Guido Tack for providing
the correspondence of global constraints of the catalogue with the constraints of
**JaCoP** and
**Gecode**.
We are also especially grateful to Sophie Demassey both,
for creating the on-line version of the catalogue (http://www.emn.fr/x-info/sdemasse/gccat/) and
for writing down the entry related to the cumulative longest hole problems,
to Helmut Simonis both, for designing the XML schema (see Section 4.5.2)
for the global constraints and their arguments, for providing the corresponding generation programs,
for providing data for several rectangle placement problems,
and for providing the code for generating the figures that display the number of solutions of a constraint
wrt some of their parameters,
and to Pierre Flener and Justin Pearson for
providing feedback with respect to the **Symmetry** slot of global constraints.
Moreover Eliane Vacheret helps for structuring many
exercises of the **Quiz** slot of the core constraints and did a first version of the
online version constraint course,
and Pierre Flener provides additional feedback on the exercises
on the core constraints.

The geometric constraints $\mathrm{\U0001d690\U0001d68e\U0001d698\U0001d69c\U0001d69d}$ and $\mathrm{\U0001d69f\U0001d692\U0001d69c\U0001d692\U0001d68b\U0001d695\U0001d68e}$ as well as the constraints related to the Region Connection Calculus where integrated within the catalogue while working on the European Union Sixth Framework Programme Contract FP6-034691 “Net-WMS”.

The glue matrices of the automata were first worked out by María Andreína Francisco Rodríguez and Nicolas Beldiceanu, and latter on systematically tested with a program by Mats Carlsson.

Finally, we want to acknowledge the continuing support of SICS and EMN for providing excellent working conditions over the years. The part of this work related to graph properties in Chapter 5 was done while the corresponding author was working at SICS.

Readers may send their suggestions via email to the corresponding author with `catalogue` as subject.

*Uppsala, Sweden, August 2003 – Nantes, France, April 2014* — NB, MC, JXR