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.