1. Preface

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 354 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 has been related to the fact that we want to express explicitly the meaning of global constraints in terms of meta -data. Finding an appropriate and concise description that easily captures the meaning of most 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.

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 use 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).

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.1. 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, 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, Gregor Baues, Christian Bessière, Éric Bourreau, 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, Pierre Flener, Xavier Gandibleux, Yan Georget, Dávid Hanák, Emmanuel Hebrard, Fabien Hermenier, Han J. A. Hoogeveen, Giuseppe F. Italiano, Antoine Jouglet, Narendra Jussien, Irit Katriel, Waldemar Kocjan, Per Kreuger, Krzysztof Kuchcinski, Mikael Zayenz Lagerkvist, Michel Leconte, Christophe Lecoutre, Xavier Lorca, Michael Marte, Julien Martin, Julien Menana, Per Mildner, Nicolas Museux, Justin Pearson, Gilles Pesant, Thierry Petit, Emmanuel Poder, Charles Prud'homme, Luis Quesada, Jean -Charles Régin, Guillaume Rochart, Xavier Savalle, Pierre Schaus, Helmut Simonis, Péter Szeredi, Radoslaw Szymanek, Guido Tack, Sven Thiel, Charlotte Truchet, Willem -Jan van Hoeve, Richard J. Wallace, Toby Walsh and Stéphane Zampelli for 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 𝚍𝚘𝚖_𝚛𝚎𝚊𝚌𝚑𝚊𝚋𝚒𝚕𝚒𝚝𝚢, the 𝚜𝚞𝚋𝚐𝚛𝚊𝚙𝚑_𝚒𝚜𝚘𝚖𝚘𝚛𝚙𝚑𝚒𝚜𝚖 and 𝚐𝚛𝚊𝚙𝚑_𝚒𝚜𝚘𝚖𝚘𝚛𝚙𝚑𝚒𝚜𝚖 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.4.2) for the global constraints and their parameters, for providing the corresponding generation programs and for providing data for several rectangle placement problems, and to Pierre Flener and Justin Pearson for providing feedback with respect to the Symmetry slot of global constraints.

The geometric constraints 𝚐𝚎𝚘𝚜𝚝 and 𝚟𝚒𝚜𝚒𝚋𝚕𝚎 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”.

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 suggestion via email to the corresponding author with catalogue as subject.

Uppsala, Sweden, August 2003 – Nantes, France, November 2010 — NB, MC, JXR