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{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$, $\mathrm{𝚌𝚢𝚌𝚕𝚎}$ or $\mathrm{𝚝𝚛𝚎𝚎}$. 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{𝚍𝚘𝚖}\_\mathrm{𝚛𝚎𝚊𝚌𝚑𝚊𝚋𝚒𝚕𝚒𝚝𝚢}$, the $\mathrm{𝚜𝚞𝚋𝚐𝚛𝚊𝚙𝚑}\_\mathrm{𝚒𝚜𝚘𝚖𝚘𝚛𝚙𝚑𝚒𝚜𝚖}$ and $\mathrm{𝚐𝚛𝚊𝚙𝚑}\_\mathrm{𝚒𝚜𝚘𝚖𝚘𝚛𝚙𝚑𝚒𝚜𝚖}$ 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{𝚐𝚎𝚘𝚜𝚝}$ and $\mathrm{𝚟𝚒𝚜𝚒𝚋𝚕𝚎}$ 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