2.3.1. Basic ideas and illustrative example

Within the graph-based representation, a global constraint is represented as a digraph where each vertex corresponds to a variable and each arc to a binary arc constraint between the variables associated with the extremities of the corresponding arc. The main difference with classical constraint networksΒ [DechterPearl87], stems from the fact that we do not force any more all arc constraints to hold. We rather consider this graph from which we discard all the arc constraints that do not hold as well as all isolated vertices (i.e, vertices not involved any more in any arc) and impose one or several graph properties on this remaining graph. These properties can for instance be a restriction on the number of connected components, on the size of the smallest connected component or on the size of the largest connected component.

Figure 2.3.1. Illustration of the link between graph-properties and global constraints
ctrs/preface-5-tikz

EXAMPLE: We give an example of interpretation of such graph properties in terms of global constraints. For this purpose we consider the sequence s of values 1 3 1 1 2 8 8 2 3 6 8 8 3 from which we construct the following graph G:

  • To each value associated with a position in s corresponds a vertex of G,

  • There is an arc from a vertex v 1 to a vertex v 2 if these vertices correspond to the same value.

FigureΒ 2.3.1 depicts graph G. Since G is symmetric, we omit the directions of the arcs. We have the following correspondence between graph properties and constraints on the sequence s:

  • The number of connected components of G corresponds to the number of distinct values of s.

  • The size of the smallest connected component of G is the smallest number of occurrences of the same value in s.

  • The size of the largest connected component of G is the largest number of occurrences of the same value in s.

As a result, in this context, putting a restriction on the number of connected components of G can been seen as a global constraint on the number of distinct values of a sequence of variables. Similar global constraints can be associated with the two other graph properties.

Β 

We now explain how to generate the initial graph associated with a global constraint. A global constraint has one or more arguments, which usually correspond to an integer value, to one variable or to a collection of variables. Therefore we have to describe the process that allows for generating the vertices and the arcs of the initial graph from the arguments of a global constraint under consideration. For this purpose we will take a concrete example.

Consider the constraint πš—πšŸπšŠπš•πšžπšŽ(π™½πš…π™°π™»,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚) where π™½πš…π™°π™» and πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ respectively correspond to a domain variable and to a collection of domain variables βŒ©πšŸπšŠπš›-V 1 ,πšŸπšŠπš›-V 2 ,β‹―,πšŸπšŠπš›-V m βŒͺ.πšŸπšŠπš› corresponds to the name of the attribute used in the collection of variables. This constraint holds if π™½πš…π™°π™» is equal to the number of distinct values assigned to the variables V 1 ,V 2 ,β‹―,V m . We first show how to generate the initial graph associated with the πš—πšŸπšŠπš•πšžπšŽ constraint. We then describe the arc constraint associated with each arc of this graph. Finally, we give the graph property we impose on the final graph.

To each variable of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds a vertex of the initial graph. We generate an arc between each pair of vertices. To each arc, we associate an equality constraint between the variables corresponding to the extremities of that arc. We impose that π™½πš…π™°π™», the variable corresponding to the first argument of πš—πšŸπšŠπš•πšžπšŽ, be equal to the number of strongly connected components of the final graph. This final graph consists of the initial graph from which we discard all arcs such that the corresponding equality constraint does not hold.

PartΒ (A) of FigureΒ 2.3.2 shows the graph initially generated for the constraint πš—πšŸπšŠπš•πšžπšŽ

(π™½πš…π™°π™»,βŒ©πšŸπšŠπš›-V 1 ,πšŸπšŠπš›-V 2 ,πšŸπšŠπš›-V 3 ,πšŸπšŠπš›-V 4 βŒͺ), where π™½πš…π™°π™», V 1 , V 2 , V 3 and V 4 are domain variables. PartΒ (B) presents the final graph associated with the ground instance πš—πšŸπšŠπš•πšžπšŽ(3,βŒ©πšŸπšŠπš›-5,πšŸπšŠπš›-5,πšŸπšŠπš›-1,πšŸπšŠπš›-8βŒͺ). For each vertex of the initial and final graph we respectively indicate the corresponding variable and the value assigned to that variable. We have removed from the final graph all the arcs associated with equalities that do not hold. The constraint πš—πšŸπšŠπš•πšžπšŽ(3,βŒ©πšŸπšŠπš›-5,πšŸπšŠπš›-5,πšŸπšŠπš›-1,πšŸπšŠπš›-8βŒͺ) holds since the final graph contains three strongly connected components, which in the context of the definition of the πš—πšŸπšŠπš•πšžπšŽ constraint, can be reinterpreted as the fact that π™½πš…π™°π™» is the number of distinct values assigned to variables V 1 ,V 2 ,V 3 ,V 4 .

Figure 2.3.2. (A) Initial and (B) final graph associated with the constraint πš—πšŸπšŠπš•πšžπšŽ(3,βŒ©πšŸπšŠπš›-5,πšŸπšŠπš›-5,πšŸπšŠπš›-1,πšŸπšŠπš›-8βŒͺ)
ctrs/preface-6-tikz

Now that we have illustrated the basic ideas for describing a global constraint in terms of graph properties, we go into more details.