Global Constraint Catalog: Cgroup

5.172. group

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

CHIP

Constraint

$𝚐𝚛𝚘𝚞𝚙 (\begin{matrix} 𝙽𝙶𝚁𝙾𝚄𝙿, \\ 𝙼𝙸𝙽_𝚂𝙸𝚉𝙴, \\ 𝙼𝙰𝚇_𝚂𝙸𝚉𝙴, \\ 𝙼𝙸𝙽_𝙳𝙸𝚂𝚃, \\ 𝙼𝙰𝚇_𝙳𝙸𝚂𝚃, \\ 𝙽𝚅𝙰𝙻, \\ 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, \\ 𝚅𝙰𝙻𝚄𝙴𝚂 \end{matrix})$

Arguments

$𝙽𝙶𝚁𝙾𝚄𝙿$	$𝚍𝚟𝚊𝚛$
$𝙼𝙸𝙽_𝚂𝙸𝚉𝙴$	$𝚍𝚟𝚊𝚛$
$𝙼𝙰𝚇_𝚂𝙸𝚉𝙴$	$𝚍𝚟𝚊𝚛$
$𝙼𝙸𝙽_𝙳𝙸𝚂𝚃$	$𝚍𝚟𝚊𝚛$
$𝙼𝙰𝚇_𝙳𝙸𝚂𝚃$	$𝚍𝚟𝚊𝚛$
$𝙽𝚅𝙰𝙻$	$𝚍𝚟𝚊𝚛$
$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$
$𝚅𝙰𝙻𝚄𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚕 - 𝚒𝚗𝚝)$

Restrictions

𝙽𝙶𝚁𝙾𝚄𝙿 \geq 0

𝙼𝙸𝙽_𝚂𝙸𝚉𝙴 \geq 0

𝙼𝙰𝚇_𝚂𝙸𝚉𝙴 \geq 𝙼𝙸𝙽_𝚂𝙸𝚉𝙴

𝙼𝙸𝙽_𝙳𝙸𝚂𝚃 \geq 0

𝙼𝙰𝚇_𝙳𝙸𝚂𝚃 \geq 𝙼𝙸𝙽_𝙳𝙸𝚂𝚃

𝙼𝙰𝚇_𝙳𝙸𝚂𝚃 \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

𝙽𝚅𝙰𝙻 \geq 𝙼𝙰𝚇_𝚂𝙸𝚉𝙴

𝙽𝚅𝙰𝙻 \geq 𝙽𝙶𝚁𝙾𝚄𝙿

𝙽𝚅𝙰𝙻 \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚟𝚊𝚛)

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝙻𝚄𝙴𝚂, 𝚟𝚊𝚕)

𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝

(𝚅𝙰𝙻𝚄𝙴𝚂, 𝚟𝚊𝚕)

Purpose

Let $n$ be the number of variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ . Let $X_{i}, X_{i + 1}, \dots, X_{j}$ $(1 \leq i \leq j \leq n)$ be consecutive variables of the collection of variables $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ such that all the following conditions simultaneously apply:

All variables $X_{i}, \dots, X_{j}$ take their value in the set of values $𝚅𝙰𝙻𝚄𝙴𝚂$ ,
$i = 1$ or $X_{i - 1}$ does not take a value in $𝚅𝙰𝙻𝚄𝙴𝚂$ ,
$j = n$ or $X_{j + 1}$ does not take a value in $𝚅𝙰𝙻𝚄𝙴𝚂$ .

We call such a sequence of variables a group. Similarly an anti-group is a maximum sequence of variables that are not assigned any value from $𝚅𝙰𝙻𝚄𝙴𝚂$ . The constraint $𝚐𝚛𝚘𝚞𝚙$ is true if all the following conditions hold:

There are exactly $𝙽𝙶𝚁𝙾𝚄𝙿$ groups of variables,
$𝙼𝙸𝙽_𝚂𝙸𝚉𝙴$ is the number of variables of the smallest group,
$𝙼𝙰𝚇_𝚂𝙸𝚉𝙴$ is the number of variables of the largest group,
$𝙼𝙸𝙽_𝙳𝙸𝚂𝚃$ is the number of variables of the smallest anti-group,
$𝙼𝙰𝚇_𝙳𝙸𝚂𝚃$ is the number of variables of the largest anti-group,
$𝙽𝚅𝙰𝙻$ is the number of variables that take their value in the set of values $𝚅𝙰𝙻𝚄𝙴𝚂$ .

Example

(2, 1, 2, 2, 4, 3, 〈2, 8, 1, 7, 4, 5, 1, 1, 1〉, 〈0, 2, 4, 6, 8〉)

Given the fact that groups are formed by even values in ${0, 2, 4, 6, 8}$ (i.e., values expressed by the $𝚅𝙰𝙻𝚄𝙴𝚂$ collection), the $𝚐𝚛𝚘𝚞𝚙$ constraint holds since:

Its first argument, $𝙽𝙶𝚁𝙾𝚄𝙿$ , is set to value 2 since the sequence $281745111$ contains two groups of even values (i.e., group $28$ and group 4).
Its second argument, $𝙼𝙸𝙽_𝚂𝙸𝚉𝙴$ , is set to value 1 since the smallest group of even values involves only a single value (i.e., value 4).
Its third argument, $𝙼𝙰𝚇_𝚂𝙸𝚉𝙴$ , is set to value 2 since the largest group of even values involves two values (i.e., group $28$ ).
Its fourth argument, $𝙼𝙸𝙽_𝙳𝙸𝚂𝚃$ , is set to value 2 since the smallest anti-group involves two values (i.e., anti-group $17$ ).
Its fifth argument, $𝙼𝙰𝚇_𝙳𝙸𝚂𝚃$ , is set to value 4 since the largest anti-group involves four values (i.e., anti-group $5111$ ).
Its sixth argument, $𝙽𝚅𝙰𝙻$ , is set to value 3 since the total number of even values of the sequence $281745111$ is equal to 3 (i.e., values 2, 8 and 4).

All solutions

Figure 5.172.1 gives all solutions to the following non ground instance of the $𝚐𝚛𝚘𝚞𝚙$ constraint: $𝙽𝙶𝚁𝙾𝚄𝙿 \in [2, 3]$ , $𝙼𝙸𝙽_𝚂𝙸𝚉𝙴 \in [3, 4]$ , $𝙼𝙰𝚇_𝚂𝙸𝚉𝙴 \in [3, 5]$ , $𝙼𝙸𝙽_𝙳𝙸𝚂𝚃 \in [1, 2]$ , $𝙼𝙰𝚇_𝙳𝙸𝚂𝚃 \in [1, 2]$ , $𝙽𝚅𝙰𝙻 \in [5, 6]$ , $V_{1} \in [0, 1]$ , $V_{2} \in [0, 1]$ , $V_{3} \in [0, 1]$ , $V_{4} \in [0, 1]$ , $V_{5} \in [0, 1]$ , $V_{6} \in [0, 1]$ , $V_{7} \in [0, 1]$ , $V_{8} \in [0, 1]$ , $V_{9} \in [0, 1]$ , $𝚐𝚛𝚘𝚞𝚙$ $(𝙽𝙶𝚁𝙾𝚄𝙿, 𝙼𝙸𝙽_𝚂𝙸𝚉𝙴, 𝙼𝙰𝚇_𝚂𝙸𝚉𝙴, 𝙼𝙸𝙽_𝙳𝙸𝚂𝚃, 𝙼𝙰𝚇_𝙳𝙸𝚂𝚃, 𝙽𝚅𝙰𝙻,$ $〈 V_{1}, V_{2}, V_{3}, V_{4}, V_{5}, V_{6}, V_{7}, V_{8}, V_{9} 〉, 〈 1 〉)$ ,

Figure 5.172.1. All solutions corresponding to the non ground example of the $𝚐𝚛𝚘𝚞𝚙$ constraint of the All solutions slot

Typical

𝙽𝙶𝚁𝙾𝚄𝙿 > 0

𝙼𝙸𝙽_𝚂𝙸𝚉𝙴 > 0

𝙼𝙰𝚇_𝚂𝙸𝚉𝙴 > 𝙼𝙸𝙽_𝚂𝙸𝚉𝙴

𝙼𝙸𝙽_𝙳𝙸𝚂𝚃 > 0

𝙼𝙰𝚇_𝙳𝙸𝚂𝚃 > 𝙼𝙸𝙽_𝙳𝙸𝚂𝚃

𝙼𝙰𝚇_𝙳𝙸𝚂𝚃 < | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

𝙽𝚅𝙰𝙻 > 𝙼𝙰𝚇_𝚂𝙸𝚉𝙴

𝙽𝚅𝙰𝙻 > 𝙽𝙶𝚁𝙾𝚄𝙿

𝙽𝚅𝙰𝙻 < | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | > 1

𝚛𝚊𝚗𝚐𝚎

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) > 1

| 𝚅𝙰𝙻𝚄𝙴𝚂 | > 0

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | > | 𝚅𝙰𝙻𝚄𝙴𝚂 |

Symmetries

Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ can be reversed.
Items of $𝚅𝙰𝙻𝚄𝙴𝚂$ are permutable.
An occurrence of a value of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ that belongs to $𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚟𝚊𝚕$ (resp. does not belong to $𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚟𝚊𝚕$ ) can be replaced by any other value in $𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚟𝚊𝚕$ (resp. not in $𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚟𝚊𝚕$ ).

Arg. properties

Functional dependency: $𝙽𝙶𝚁𝙾𝚄𝙿$ determined by $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ and $𝚅𝙰𝙻𝚄𝙴𝚂$ .
Functional dependency: $𝙼𝙸𝙽_𝚂𝙸𝚉𝙴$ determined by $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ and $𝚅𝙰𝙻𝚄𝙴𝚂$ .
Functional dependency: $𝙼𝙰𝚇_𝚂𝙸𝚉𝙴$ determined by $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ and $𝚅𝙰𝙻𝚄𝙴𝚂$ .
Functional dependency: $𝙼𝙸𝙽_𝙳𝙸𝚂𝚃$ determined by $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ and $𝚅𝙰𝙻𝚄𝙴𝚂$ .
Functional dependency: $𝙼𝙰𝚇_𝙳𝙸𝚂𝚃$ determined by $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ and $𝚅𝙰𝙻𝚄𝙴𝚂$ .
Functional dependency: $𝙽𝚅𝙰𝙻$ determined by $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ and $𝚅𝙰𝙻𝚄𝙴𝚂$ .

Usage

A typical use of the $𝚐𝚛𝚘𝚞𝚙$ constraint in the context of timetabling is as follow: The value of the $i^{t h}$ variable of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection corresponds to the type of shift (i.e., night, morning, afternoon, rest) performed by a specific person on day $i$ . A complete period of work is represented by the variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection. In this context the $𝚐𝚛𝚘𝚞𝚙$ constraint expresses for a person:

The number of periods of consecutive night-shift during a complete period of work.
The total number of night-shift during a complete period of work.
The maximum number of allowed consecutive night-shift.
The minimum number of days, which do not correspond to a night-shift, between two consecutive sequences of night-shift.

Remark

For this constraint we use the possibility to express directly more than one constraint on the parameters of the final graph we want to obtain. For more propagation, it is crucial to keep this in a single constraint, since strong relations relate the different parameters of a graph. This constraint is very similar to the $𝚐𝚛𝚘𝚞𝚙$ constraint introduced in CHIP, except that here, the $𝙼𝙸𝙽_𝙳𝙸𝚂𝚃$ and $𝙼𝙰𝚇_𝙳𝙸𝚂𝚃$ constraints apply also for the two borders: we cannot start or end with a group of $k$ consecutive variables that take their values outside $𝚅𝙰𝙻𝚄𝙴𝚂$ and such that $k$ is less than $𝙼𝙸𝙽_𝙳𝙸𝚂𝚃$ or $k$ is greater than $𝙼𝙰𝚇_𝙳𝙸𝚂𝚃$ .

$𝚐𝚛𝚘𝚞𝚙_𝚜𝚔𝚒𝚙_𝚒𝚜𝚘𝚕𝚊𝚝𝚎𝚍_𝚒𝚝𝚎𝚖$ (timetabling constraint,sequence),

$𝚖𝚞𝚕𝚝𝚒_𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚘𝚗𝚝𝚒𝚐𝚞𝚒𝚝𝚢$ (sequence),

$𝚙𝚊𝚝𝚝𝚎𝚛𝚗$ , $𝚜𝚝𝚛𝚎𝚝𝚌𝚑_𝚌𝚒𝚛𝚌𝚞𝚒𝚝$ (timetabling constraint),

$𝚜𝚝𝚛𝚎𝚝𝚌𝚑_𝚙𝚊𝚝𝚑$ (timetabling constraint,sequence).

shift of concept: $𝚌𝚘𝚗𝚜𝚎𝚌𝚞𝚝𝚒𝚟𝚎_𝚐𝚛𝚘𝚞𝚙𝚜_𝚘𝚏_𝚘𝚗𝚎𝚜$ .

used in graph description: $𝚒𝚗$ , $𝚗𝚘𝚝_𝚒𝚗$ .

Keywords

characteristic of a constraint: automaton, automaton with counters, automaton with same input symbol.

combinatorial object: sequence.

constraint arguments: reverse of a constraint, pure functional dependency.

constraint network structure: alpha-acyclic constraint network(2), alpha-acyclic constraint network(3).

constraint type: timetabling constraint.

filtering: glue matrix.

final graph structure: connected component, vpartition, consecutive loops are connected.

modelling: functional dependency.

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$

Arc generator

𝑃𝐴𝑇𝐻

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1, 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2)

𝐿𝑂𝑂𝑃

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1, 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2)

Arc arity

Arc constraint(s)

•

𝚒𝚗

(𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1 . 𝚟𝚊𝚛, 𝚅𝙰𝙻𝚄𝙴𝚂)

•

𝚒𝚗

(𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2 . 𝚟𝚊𝚛, 𝚅𝙰𝙻𝚄𝙴𝚂)

Graph property(ies)

•

𝐍𝐂𝐂

= 𝙽𝙶𝚁𝙾𝚄𝙿

•

𝐌𝐈𝐍_𝐍𝐂𝐂

= 𝙼𝙸𝙽_𝚂𝙸𝚉𝙴

•

𝐌𝐀𝐗_𝐍𝐂𝐂

= 𝙼𝙰𝚇_𝚂𝙸𝚉𝙴

•

𝐍𝐕𝐄𝐑𝐓𝐄𝐗

= 𝙽𝚅𝙰𝙻

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$

Arc generator

𝑃𝐴𝑇𝐻

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1, 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2)

𝐿𝑂𝑂𝑃

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1, 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2)

Arc arity

Arc constraint(s)

•

𝚗𝚘𝚝_𝚒𝚗

(𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1 . 𝚟𝚊𝚛, 𝚅𝙰𝙻𝚄𝙴𝚂)

•

𝚗𝚘𝚝_𝚒𝚗

(𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2 . 𝚟𝚊𝚛, 𝚅𝙰𝙻𝚄𝙴𝚂)

Graph property(ies)

•

𝐌𝐈𝐍_𝐍𝐂𝐂

= 𝙼𝙸𝙽_𝙳𝙸𝚂𝚃

•

𝐌𝐀𝐗_𝐍𝐂𝐂

= 𝙼𝙰𝚇_𝙳𝙸𝚂𝚃

Graph model

We use two graph constraints for modelling the $𝚐𝚛𝚘𝚞𝚙$ constraint: a first one for specifying the constraints on $𝙽𝙶𝚁𝙾𝚄𝙿$ , $𝙼𝙸𝙽_𝚂𝙸𝚉𝙴$ , $𝙼𝙰𝚇_𝚂𝙸𝚉𝙴$ and $𝙽𝚅𝙰𝙻$ , and a second one for stating the constraints on $𝙼𝙸𝙽_𝙳𝙸𝚂𝚃$ and $𝙼𝙰𝚇_𝙳𝙸𝚂𝚃$ . In order to generate the initial graph related to the first graph constraint we use:

The arc generators $𝑃𝐴𝑇𝐻$ and $𝐿𝑂𝑂𝑃$ ,
The binary constraint $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1 . 𝚟𝚊𝚛 \in 𝚅𝙰𝙻𝚄𝙴𝚂 \land 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2 . 𝚟𝚊𝚛 \in 𝚅𝙰𝙻𝚄𝙴𝚂$ .

On the first graph constraint of the Example slot this produces an initial graph depicted in part (A) of Figure 5.172.2. We use $𝑃𝐴𝑇𝐻$ $𝐿𝑂𝑂𝑃$ and the binary constraint $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1 . 𝚟𝚊𝚛 \in 𝚅𝙰𝙻𝚄𝙴𝚂 \land 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2 . 𝚟𝚊𝚛 \in 𝚅𝙰𝙻𝚄𝙴𝚂$ in order to catch the two following situations:

A binary constraint has to be used in order to get the notion of group: Consecutive variables that take their value in $𝚅𝙰𝙻𝚄𝙴𝚂$ .
If we only use $𝑃𝐴𝑇𝐻$ then we would lose the groups that are composed from a single variable since the predecessor and the successor arc would be destroyed; this is why we use also the $𝐿𝑂𝑂𝑃$ arc generator.

Part (B) of Figure 5.172.2 shows the final graph associated with the first graph constraint of the Example slot. Since we use the $𝐍𝐕𝐄𝐑𝐓𝐄𝐗$ graph property, the vertices of the final graph are stressed in bold. In addition, since we use the $𝐌𝐈𝐍_𝐍𝐂𝐂$ and the $𝐌𝐀𝐗_𝐍𝐂𝐂$ graph properties, we also show the smallest and largest connected components of the final graph.

Figure 5.172.2. Initial and final graph of the $𝚐𝚛𝚘𝚞𝚙$ constraint


(a)	(b)

The $𝚐𝚛𝚘𝚞𝚙$ constraint of the Example slot holds since:

The final graph of the first graph constraint has two connected components. Therefore the number of groups $𝙽𝙶𝚁𝙾𝚄𝙿$ is equal to two.
The number of vertices of the smallest connected component of the final graph of the first graph constraint is equal to 1. Therefore $𝙼𝙸𝙽_𝚂𝙸𝚉𝙴$ is equal to 1.
The number of vertices of the largest connected component of the final graph of the first graph constraint is equal to 2. Therefore $𝙼𝙰𝚇_𝚂𝙸𝚉𝙴$ is equal to 2.
The number of vertices of the smallest connected component of the final graph of the second graph constraint is equal to 2. Therefore $𝙼𝙸𝙽_𝙳𝙸𝚂𝚃$ is equal to 2.
The number of vertices of the largest connected component of the final graph of the second graph constraint is equal to 4. Therefore $𝙼𝙰𝚇_𝙳𝙸𝚂𝚃$ is equal to 4.
The number of vertices of the final graph of the first graph constraint is equal to three. Therefore $𝙽𝚅𝙰𝙻$ is equal to 3.

Automaton: Figures 5.172.3, 5.172.5, 5.172.8, 5.172.10, 5.172.12 and 5.172.14 depict the different automata associated with the $𝚐𝚛𝚘𝚞𝚙$ constraint. For the automata that respectively compute $𝙽𝙶𝚁𝙾𝚄𝙿$ , $𝙼𝙸𝙽_𝚂𝙸𝚉𝙴$ , $𝙼𝙰𝚇_𝚂𝙸𝚉𝙴$ , $𝙼𝙸𝙽_𝙳𝙸𝚂𝚃$ , $𝙼𝙰𝚇_𝙳𝙸𝚂𝚃$ and $𝙽𝚅𝙰𝙻$ we have a 0-1 signature variable $𝚂_{i}$ for each variable ${𝚅𝙰𝚁}_{i}$ of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ . The following signature constraint links ${𝚅𝙰𝚁}_{i}$ and $𝚂_{i}$ : ${𝚅𝙰𝚁}_{i} \in 𝚅𝙰𝙻𝚄𝙴𝚂 \Leftrightarrow 𝚂_{i}$ .

Figure 5.172.3. Automaton for the $𝙽𝙶𝚁𝙾𝚄𝙿$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint and its glue matrix

Figure 5.172.4. Hypergraph of the reformulation corresponding to the automaton (with one counter) of the $𝙽𝙶𝚁𝙾𝚄𝙿$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint (since all states of the automaton are accepting there is no restriction on the last variable $Q_{n}$ )

Figure 5.172.5. Automaton for the $𝙼𝙸𝙽_𝚂𝙸𝚉𝙴$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint and its glue matrix

Figure 5.172.6. Illustrating the use of the state pair $(i, i)$ of the glue matrix for linking $𝙼𝙸𝙽_𝚂𝙸𝚉𝙴$ with the counters variables obtained after reading the prefix $0, 1, 1, 1, 0, 0, 1$ and corresponding suffix $1, 0, 1, 1, 1, 1$ of the sequence $0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1$ ; note that the suffix $1, 0, 1, 1, 1, 1$ (in pink) is proceed in reverse order; the left (resp. right) table shows the initialisation (for $i = 0$ ) and the evolution (for $i > 0$ ) of the state of the automaton and its counters $C$ and $D$ upon reading the prefix $0, 1, 1, 1, 0, 0, 1$ (resp. the reverse suffix $1, 1, 1, 1, 0, 1$ ).

Figure 5.172.7. Hypergraph of the reformulation corresponding to the automaton (with two counters) of the $𝙼𝙸𝙽_𝚂𝙸𝚉𝙴$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint where $𝙽$ stands for $| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |$ (since all states of the automaton are accepting there is no restriction on the last variable $Q_{n}$ )

Figure 5.172.8. Automaton for the $𝙼𝙰𝚇_𝚂𝙸𝚉𝙴$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint and its glue matrix

Figure 5.172.9. Hypergraph of the reformulation corresponding to the automaton (with two counters) of the $𝙼𝙰𝚇_𝚂𝙸𝚉𝙴$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint

Figure 5.172.10. Automaton for the $𝙼𝙸𝙽_𝙳𝙸𝚂𝚃$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint and its glue matrix

Figure 5.172.11. Hypergraph of the reformulation corresponding to the automaton (with two counters) of the $𝙼𝙸𝙽_𝙳𝙸𝚂𝚃$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint where $𝙽$ stands for $| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |$ (since all states of the automaton are accepting there is no restriction on the last variable $Q_{n}$ )

Figure 5.172.12. Automaton for the $𝙼𝙰𝚇_𝙳𝙸𝚂𝚃$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint and its glue matrix

Figure 5.172.13. Hypergraph of the reformulation corresponding to the automaton (with two counters) of the $𝙼𝙰𝚇_𝙳𝙸𝚂𝚃$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint

Figure 5.172.14. Automaton for the $𝙽𝚅𝙰𝙻$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint and its glue matrix

Figure 5.172.15. Hypergraph of the reformulation corresponding to the automaton (with one counter) of the $𝙽𝚅𝙰𝙻$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.172. group

Figure 5.172.1. All solutions corresponding to the non ground example of the $𝚐𝚛𝚘𝚞𝚙$ constraint of the All solutions slot

Figure 5.172.2. Initial and final graph of the $𝚐𝚛𝚘𝚞𝚙$ constraint

Figure 5.172.3. Automaton for the $𝙽𝙶𝚁𝙾𝚄𝙿$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint and its glue matrix

Figure 5.172.4. Hypergraph of the reformulation corresponding to the automaton (with one counter) of the $𝙽𝙶𝚁𝙾𝚄𝙿$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint (since all states of the automaton are accepting there is no restriction on the last variable $Q_{n}$ )

Figure 5.172.5. Automaton for the $𝙼𝙸𝙽_𝚂𝙸𝚉𝙴$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint and its glue matrix

Figure 5.172.8. Automaton for the $𝙼𝙰𝚇_𝚂𝙸𝚉𝙴$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint and its glue matrix

Figure 5.172.9. Hypergraph of the reformulation corresponding to the automaton (with two counters) of the $𝙼𝙰𝚇_𝚂𝙸𝚉𝙴$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint

Figure 5.172.10. Automaton for the $𝙼𝙸𝙽_𝙳𝙸𝚂𝚃$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint and its glue matrix

Figure 5.172.12. Automaton for the $𝙼𝙰𝚇_𝙳𝙸𝚂𝚃$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint and its glue matrix

Figure 5.172.13. Hypergraph of the reformulation corresponding to the automaton (with two counters) of the $𝙼𝙰𝚇_𝙳𝙸𝚂𝚃$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint

Figure 5.172.14. Automaton for the $𝙽𝚅𝙰𝙻$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint and its glue matrix

Figure 5.172.15. Hypergraph of the reformulation corresponding to the automaton (with one counter) of the $𝙽𝚅𝙰𝙻$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.172. group

Figure 5.172.1. All solutions corresponding to the non ground example of the 𝚐𝚛𝚘𝚞𝚙 constraint of the All solutions slot

Figure 5.172.2. Initial and final graph of the 𝚐𝚛𝚘𝚞𝚙 constraint

Figure 5.172.3. Automaton for the 𝙽𝙶𝚁𝙾𝚄𝙿 argument of the 𝚐𝚛𝚘𝚞𝚙 constraint and its glue matrix

Figure 5.172.4. Hypergraph of the reformulation corresponding to the automaton (with one counter) of the 𝙽𝙶𝚁𝙾𝚄𝙿 argument of the 𝚐𝚛𝚘𝚞𝚙 constraint (since all states of the automaton are accepting there is no restriction on the last variable Q n )

Figure 5.172.5. Automaton for the 𝙼𝙸𝙽_𝚂𝙸𝚉𝙴 argument of the 𝚐𝚛𝚘𝚞𝚙 constraint and its glue matrix

Figure 5.172.8. Automaton for the 𝙼𝙰𝚇_𝚂𝙸𝚉𝙴 argument of the 𝚐𝚛𝚘𝚞𝚙 constraint and its glue matrix

Figure 5.172.9. Hypergraph of the reformulation corresponding to the automaton (with two counters) of the 𝙼𝙰𝚇_𝚂𝙸𝚉𝙴 argument of the 𝚐𝚛𝚘𝚞𝚙 constraint

Figure 5.172.10. Automaton for the 𝙼𝙸𝙽_𝙳𝙸𝚂𝚃 argument of the 𝚐𝚛𝚘𝚞𝚙 constraint and its glue matrix

Figure 5.172.12. Automaton for the 𝙼𝙰𝚇_𝙳𝙸𝚂𝚃 argument of the 𝚐𝚛𝚘𝚞𝚙 constraint and its glue matrix

Figure 5.172.13. Hypergraph of the reformulation corresponding to the automaton (with two counters) of the 𝙼𝙰𝚇_𝙳𝙸𝚂𝚃 argument of the 𝚐𝚛𝚘𝚞𝚙 constraint

Figure 5.172.14. Automaton for the 𝙽𝚅𝙰𝙻 argument of the 𝚐𝚛𝚘𝚞𝚙 constraint and its glue matrix

Figure 5.172.15. Hypergraph of the reformulation corresponding to the automaton (with one counter) of the 𝙽𝚅𝙰𝙻 argument of the 𝚐𝚛𝚘𝚞𝚙 constraint

Figure 5.172.1. All solutions corresponding to the non ground example of the $𝚐𝚛𝚘𝚞𝚙$ constraint of the All solutions slot

Figure 5.172.2. Initial and final graph of the $𝚐𝚛𝚘𝚞𝚙$ constraint

Figure 5.172.3. Automaton for the $𝙽𝙶𝚁𝙾𝚄𝙿$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint and its glue matrix

Figure 5.172.4. Hypergraph of the reformulation corresponding to the automaton (with one counter) of the $𝙽𝙶𝚁𝙾𝚄𝙿$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint (since all states of the automaton are accepting there is no restriction on the last variable $Q_{n}$ )

Figure 5.172.5. Automaton for the $𝙼𝙸𝙽_𝚂𝙸𝚉𝙴$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint and its glue matrix

Figure 5.172.8. Automaton for the $𝙼𝙰𝚇_𝚂𝙸𝚉𝙴$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint and its glue matrix

Figure 5.172.9. Hypergraph of the reformulation corresponding to the automaton (with two counters) of the $𝙼𝙰𝚇_𝚂𝙸𝚉𝙴$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint

Figure 5.172.10. Automaton for the $𝙼𝙸𝙽_𝙳𝙸𝚂𝚃$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint and its glue matrix

Figure 5.172.12. Automaton for the $𝙼𝙰𝚇_𝙳𝙸𝚂𝚃$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint and its glue matrix

Figure 5.172.13. Hypergraph of the reformulation corresponding to the automaton (with two counters) of the $𝙼𝙰𝚇_𝙳𝙸𝚂𝚃$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint

Figure 5.172.14. Automaton for the $𝙽𝚅𝙰𝙻$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint and its glue matrix

Figure 5.172.15. Hypergraph of the reformulation corresponding to the automaton (with one counter) of the $𝙽𝚅𝙰𝙻$ argument of the $𝚐𝚛𝚘𝚞𝚙$ constraint