Global Constraint Catalog: Cfull

5.157. full_group

DESCRIPTION

LINKS

AUTOMATON

Origin

Constraint

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

Synonym

$𝚐𝚛𝚘𝚞𝚙_𝚠𝚒𝚝𝚑𝚘𝚞𝚝_𝚋𝚘𝚛𝚍𝚎𝚛$ .

Arguments

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

Restrictions

𝙽𝙶𝚁𝙾𝚄𝙿 \geq 0

𝙼𝙸𝙽_𝚂𝙸𝚉𝙴 \geq 0

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

𝙼𝙸𝙽_𝙳𝙸𝚂𝚃 \geq 0

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

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

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

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

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝

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

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. A full group is a group that neither starts at position 1 nor ends at position $n$ . Similarly an anti-full group is a maximum sequence of variables that are not assigned any value from $𝚅𝙰𝙻𝚄𝙴𝚂$ that neither starts at position 1 nor ends at position $n$ .

The constraint $𝚏𝚞𝚕𝚕_𝚐𝚛𝚘𝚞𝚙$ is true if all the following conditions hold:

There are exactly $𝙽𝙶𝚁𝙾𝚄𝙿$ full groups of variables,
$𝙼𝙸𝙽_𝚂𝙸𝚉𝙴$ is the number of variables of the smallest full group,
$𝙼𝙰𝚇_𝚂𝙸𝚉𝙴$ is the number of variables of the largest full group,
$𝙼𝙸𝙽_𝙳𝙸𝚂𝚃$ is the number of variables of the smallest anti-full group,
$𝙼𝙰𝚇_𝙳𝙸𝚂𝚃$ is the number of variables of the largest anti-full group,
$𝙽𝚅𝙰𝙻$ is the number of variables that belong to a full group.

Example

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

Given the fact that full 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 $012627489$ contains two full groups of even values (i.e., group $262$ and group $48$ ). Note that the first 0 is not a full group since it is located at the first position of the sequence.
Its second argument, $𝙼𝙸𝙽_𝚂𝙸𝚉𝙴$ , is set to value 2 since the smallest full group of even values involves only two elements (i.e., the full group $48$ ).
Its third argument, $𝙼𝙰𝚇_𝚂𝙸𝚉𝙴$ , is set to value 3 since the largest full group of even values involves three elements (i.e., the full group $262$ ).
Its fourth argument, $𝙼𝙸𝙽_𝙳𝙸𝚂𝚃$ , is set to value 1 since the smallest anti-full groups involve a single element (i.e., the anti-full groups 1 and 7).
Its fifth argument, $𝙼𝙰𝚇_𝙳𝙸𝚂𝚃$ , is set to value 1 since the largest anti-full groups involve a single element (i.e., the anti-full groups 1 and 7).
Its sixth argument, $𝙽𝚅𝙰𝙻$ , is set to value 5 since the total number of even values part of a full group of the sequence $012627489$ is equal to 5 (i.e., elements 2, 6, 2, 4 and 8).

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 $𝚅𝙰𝙻𝚄𝙴𝚂$ .

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.

modelling: functional dependency.

Automaton: Figures 5.157.1, 5.157.3, 5.157.5, 5.157.7, 5.157.9 and 5.157.11 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.157.1. Automaton for the $𝙽𝙶𝚁𝙾𝚄𝙿$ argument of the $𝚏𝚞𝚕𝚕_𝚐𝚛𝚘𝚞𝚙$ constraint and its glue matrix

Figure 5.157.2. 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.157.3. Automaton for the $𝙼𝙸𝙽_𝚂𝙸𝚉𝙴$ argument of the $𝚏𝚞𝚕𝚕_𝚐𝚛𝚘𝚞𝚙$ constraint

Figure 5.157.4. Hypergraph of the reformulation corresponding to the automaton (with two counters) 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.157.5. Automaton for the $𝙼𝙰𝚇_𝚂𝙸𝚉𝙴$ argument of the $𝚏𝚞𝚕𝚕_𝚐𝚛𝚘𝚞𝚙$ constraint and its glue matrix

Figure 5.157.6. Hypergraph of the reformulation corresponding to the automaton (with two counters) 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.157.7. Automaton for the $𝙼𝙸𝙽_𝙳𝙸𝚂𝚃$ argument of the $𝚏𝚞𝚕𝚕_𝚐𝚛𝚘𝚞𝚙$ constraint

Figure 5.157.8. Hypergraph of the reformulation corresponding to the automaton (with two counters) 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.157.9. Automaton for the $𝙼𝙰𝚇_𝙳𝙸𝚂𝚃$ argument of the $𝚏𝚞𝚕𝚕_𝚐𝚛𝚘𝚞𝚙$ constraint and its glue matrix

Figure 5.157.10. Hypergraph of the reformulation corresponding to the automaton (with two counters) 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.157.11. Automaton for the $𝙽𝚅𝙰𝙻$ argument of the $𝚏𝚞𝚕𝚕_𝚐𝚛𝚘𝚞𝚙$ constraint and its glue matrix

Figure 5.157.12. Hypergraph of the reformulation corresponding to the automaton (with two counters) of the $𝙽𝚅𝙰𝙻$ argument of the $𝚏𝚞𝚕𝚕_𝚐𝚛𝚘𝚞𝚙$ constraint (since all states of the automaton are accepting there is no restriction on the last variable $Q_{n}$ )

Global Constraint Catalog

5. Global Constraint Catalogue

5.157. full_group

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

Figure 5.157.3. Automaton for the $𝙼𝙸𝙽_𝚂𝙸𝚉𝙴$ argument of the $𝚏𝚞𝚕𝚕_𝚐𝚛𝚘𝚞𝚙$ constraint

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

Figure 5.157.7. Automaton for the $𝙼𝙸𝙽_𝙳𝙸𝚂𝚃$ argument of the $𝚏𝚞𝚕𝚕_𝚐𝚛𝚘𝚞𝚙$ constraint

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

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

Figure 5.157.12. Hypergraph of the reformulation corresponding to the automaton (with two counters) of the $𝙽𝚅𝙰𝙻$ argument of the $𝚏𝚞𝚕𝚕_𝚐𝚛𝚘𝚞𝚙$ constraint (since all states of the automaton are accepting there is no restriction on the last variable $Q_{n}$ )

Global Constraint Catalog

5. Global Constraint Catalogue

5.157. full_group

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

Figure 5.157.2. 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.157.3. Automaton for the 𝙼𝙸𝙽_𝚂𝙸𝚉𝙴 argument of the 𝚏𝚞𝚕𝚕_𝚐𝚛𝚘𝚞𝚙 constraint

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

Figure 5.157.7. Automaton for the 𝙼𝙸𝙽_𝙳𝙸𝚂𝚃 argument of the 𝚏𝚞𝚕𝚕_𝚐𝚛𝚘𝚞𝚙 constraint

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

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

Figure 5.157.12. Hypergraph of the reformulation corresponding to the automaton (with two counters) 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.157.1. Automaton for the $𝙽𝙶𝚁𝙾𝚄𝙿$ argument of the $𝚏𝚞𝚕𝚕_𝚐𝚛𝚘𝚞𝚙$ constraint and its glue matrix

Figure 5.157.3. Automaton for the $𝙼𝙸𝙽_𝚂𝙸𝚉𝙴$ argument of the $𝚏𝚞𝚕𝚕_𝚐𝚛𝚘𝚞𝚙$ constraint

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

Figure 5.157.7. Automaton for the $𝙼𝙸𝙽_𝙳𝙸𝚂𝚃$ argument of the $𝚏𝚞𝚕𝚕_𝚐𝚛𝚘𝚞𝚙$ constraint

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

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

Figure 5.157.12. Hypergraph of the reformulation corresponding to the automaton (with two counters) of the $𝙽𝚅𝙰𝙻$ argument of the $𝚏𝚞𝚕𝚕_𝚐𝚛𝚘𝚞𝚙$ constraint (since all states of the automaton are accepting there is no restriction on the last variable $Q_{n}$ )