# 2. Describing Global Constraints

We first introduce the notion of global constraint as well as the different facets attached to global constraints.
We then motivate the need for an explicit description of
global constraints and then present the *graph-based* as well
as the *automaton-based* descriptions used throughout the catalogue.
On the one hand, the graph-based representation considers a global constraint
as a subgraph of an initial given graph. This subgraph has to
satisfy a set of required graph properties.
On the other hand, the automaton-based representation denotes
a global constraint as a hypergraph constructed from a
given constraint checker.A *constraint checker*
is a program that takes an instance of a constraint for which all variables
are fixed and tests whether the constraint is satisfied or not.
Both, the initial graph of the graph-based representation,
as well as the hypergraph of the automaton-based representation
have a very regular structure, which should give the opportunity
for efficient filtering algorithms taking advantage of this
structure.

We now present our motivations for an explicit description
of the meaning of global constraints.
The current trendThis can be observed in all
constraint manuals where the description of the meaning
is always informal. is to first use natural language for
describing the meaning of a global constraint and second
to work out a specialised filtering algorithm. Since we
have a huge number of potential global constraints that can
be combined in a lot of ways, this is an immense task.
Since we are also interested in providing other services,
such as
*visualisation* [ZimmermannCunningham91], [SimonisAggounBeldiceanuBourreau00], [SimonisDavernFeldmanMehtaQuesadaCarlsson10],
*explanations* [RochartJussien03],
*cuts for linear programming* [HookerYan02],
*moves for local search* [Bohlin04],
*generation of clauses for SAT solvers* [Nieuwenhuis10],
*generation of multivalued decision diagrams that represent compact relaxations of global constraints* [HodaHoeveHooker10],
*soft global constraints* [PetitReginBessiere01], [BeldiceanuPetit04], [HoevePesantRousseau04],
*learning implied global constraints* [BessiereColettaPetit05],
simplifying away fixed variables from global constraints when they have the same effect on the remaining unfixed variables in order to automatically identify equivalent subproblems during search [ChuGarciadelaBandaStuckey10],
and *specialised heuristics* for each global constraint
this is even worse.
One could argue that a candidate for describing explicitly
the meaning of global constraints would be second order
predicate calculus. This could perhaps solve our description
problem but would, at least currently, not be useful for
deriving any filtering algorithm.One could perhaps use a system like
MONA [HenriksenJensenJorgensenKlarlundPaigeRauheSandholm95]
or some ideas from [BordeauxMonfroy03]
for getting a constraint checker in the context of the graph-based representation.
For a similar reason Prolog was restricted to Horn clauses
for which one had a reasonable solving mechanism.
What we want to stress through this example is the fact
that a declarative description is really useful only if it
also provides some hints about how to deal with that description.
Our first choice of a graph-based representation has been
influenced by the following observations:

The concept of graph has its roots in the area of mathematical recreations (see for instance L. Euler [Euler59], H. E. Dudeney [Dudeney19], E. Lucas [Lucas1882] and T. P. Kirkman [Kirkman1847]), which was somehow the ancestor of combinatorial problems. In this perspective a graph-based description makes sense.

In one of the first books introducing graph theory [Berge70], C. Berge presents graph theory as a way of grouping apparently diverse problems and results. This was also the case for global constraints.

The parameters associated with graphs are concrete and concise. Moreover a lot of results about graphs can be expressed in terms of graph invariants involving various graph parameters that are valid for specific graph classes. In essence, formulae are a kind of declarative statement that is much more compact than algorithms.

Finally, it is well known that graph theory is an important tool [Mehlhorn00] with respect to the development of efficient filtering algorithms [Regin94], [Regin96], [Regin99], [ReginRueher99], [MehlhornThiel00], [KatrielThiel03], [BeldiceanuKatrielThiel04b], [Hoeve04], [QuimperLopezOrtizBeekGolynski04].

Our second choice of an automaton-based representation has been
motivated by the following observation. Writing a constraint checker
is usually a straightforward task. The corresponding program can
usually be turned into an automaton. Of course an automaton is
typically used on a fixed sequence of symbols. But, in the
context of filtering algorithms, we have to deal with a sequence
of variables.
For this purpose we have
shown [BeldiceanuCarlssonPetit04]
for some automata how to decompose them into a conjunction of
smaller constraints. In this context, a global constraint can
be seen as a hypergraph corresponding to its decomposition.
The hypergraph has two types of hyperedges: the first type corresponds to
*transition constraints* describing the behavior of the automaton,
while the second type represents *signature constraints* encoding
the mapping of arguments of the constraint to symbols of the alphabet of the automaton.

- 2.1. Global constraint: what it is, and what it is not
- 2.1.1. Checker view
- 2.1.2. Feasibility view
- 2.1.3. Filtering view
- 2.1.4. Explanation view
- 2.1.5. Cost violation view
- 2.1.6. Reification view
- 2.1.7. Counting view
- 2.1.8. Property view

- 2.2. Describing the arguments of a global constraint
- 2.2.1. Basic data types
- 2.2.2. Compound data types
- 2.2.3. Restrictions
- 2.2.4. Declaring a global constraint
- 2.2.5. Describing symmetries between arguments

- 2.3. Describing global constraints in terms of graph properties
- 2.3.1. Basic ideas and illustrative example
- 2.3.2. Ingredients used for describing global constraints
- 2.3.2.1. Collection generators
- 2.3.2.2. Elementary constraints attached to the arcs
- 2.3.2.3. Graph generators
- 2.3.2.4. Graph properties

- 2.3.3. Graph constraint
- 2.3.3.1. Simple graph constraint
- 2.3.3.2. Dynamic graph constraint

- 2.4. Describing global constraints in terms of automata
- 2.5. Reformulating global constraints as a conjunction
- 2.6. Semantic links between global constraints
- 2.6.1. Assignment dimension added
- 2.6.2. Assignment dimension removed
- 2.6.3. Attached to cost variant
- 2.6.4. Common keyword
- 2.6.5. Comparison swapped
- 2.6.6. Cost variant
- 2.6.7. Generalisation
- 2.6.8. Hard version
- 2.6.9. Implied by
- 2.6.10. Implies
- 2.6.11. Implies (if swap arguments)
- 2.6.12. Implies (items to collection)
- 2.6.13. Negation
- 2.6.14. Part of system of constraints
- 2.6.15. Related
- 2.6.16. Related to a common problem
- 2.6.17. Root concept
- 2.6.18. Shift of concept
- 2.6.19. Soft variant
- 2.6.20. Specialisation
- 2.6.21. System of constraints
- 2.6.22. Used in graph description
- 2.6.23. Used in reformulation
- 2.6.24. Uses in its reformulation