Global Constraint Catalog

2.3.2.1. Collection generators

The vertices of the initial graph are usually directly generated from collections of items that are arguments of the global constraint $𝙶$ under consideration. However, it sometimes happens that we would like to derive a new collection from existing arguments of $𝙶$ in order to produce the vertices of the initial graph.

EXAMPLE: This is for instance the case of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ $(𝙸𝙽𝙳𝙴𝚇,$ $𝚃𝙰𝙱𝙻𝙴,$ $𝚅𝙰𝙻𝚄𝙴)$ constraint, where $𝙸𝙽𝙳𝙴𝚇$ and $𝚅𝙰𝙻𝚄𝙴$ are domain variables that we would like to group as a single item $ℐ$ (with two attributes) of a new derived collection. This is in fact done in order to generate the following initial graph:

The item $ℐ$ as well as all items of $𝚃𝙰𝙱𝙻𝙴$ constitute the vertices,
There is an arc from $ℐ$ to each item of the $𝚃𝙰𝙱𝙻𝙴$ collection.

We provide the following mechanism for deriving new collections:

In a first phase we declare the name of the new collection as well as the names of its attributes and their respective types. This is achieved exactly in the same way as those collections that are used in the arguments of a global constraint (see page 2.2.2).

EXAMPLE: Consider again the example of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ $(𝙸𝙽𝙳𝙴𝚇,$ $𝚃𝙰𝙱𝙻𝙴,$ $𝚅𝙰𝙻𝚄𝙴)$ constraint. The declaration $𝙸𝚃𝙴𝙼 - 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚒𝚗𝚍𝚎𝚡 - 𝚍𝚟𝚊𝚛, 𝚟𝚊𝚕𝚞𝚎 - 𝚍𝚟𝚊𝚛)$ introduces a new collection called $𝙸𝚃𝙴𝙼$ where each item has an $𝚒𝚗𝚍𝚎𝚡$ and a $𝚟𝚊𝚕𝚞𝚎$ attribute. Both attributes correspond to domain variables.
In a second phase we give a list of patterns that are used for generating the items of the new collection. A pattern $o - 𝚒𝚝𝚎𝚖 (𝚊_{1} - v_{1}, 𝚊_{2} - v_{2}, \dots, 𝚊_{n} - v_{n})$ or $𝚒𝚝𝚎𝚖 (𝚊_{1} - v_{1}, 𝚊_{2} - v_{2}, \dots, 𝚊_{n} - v_{n})$ specifies for each attribute $𝚊_{i} (1 \leq i \leq n)$ of the new collection how to fill it. $o$ is one of the comparison operators $=, \neq, <, \geq, >, \leq$ . When omitted its default value is $=$ . This is done by providing for each attribute $𝚊_{i}$ one of the following expression $v_{i}$ :
- A constant.
- An argument of the global constraint $𝙶$ .
- An expression $𝚌 . 𝚊$ , where $𝚊$ is an attribute of a collection $𝚌$ , such that $𝚌$ is an argument of the global constraint $𝙶$ or a derived collection that was previously declared. An expression of this form is called a direct reference to an attribute of a collection.
- An expression $𝚌_{1} . 𝚌_{2} . 𝚊$ , where $𝚊$ is an attribute of a collection $𝚌_{2}$ , and $𝚌_{2}$ is an attribute of a collection $𝚌_{1}$ such that $𝚌_{1}$ is an argument of the global constraint $𝙶$ or a derived collection that was previously declared. An expression of this form is called an indirect reference to an attribute of a collection.
This expression $v_{i}$ must be compatible with the type declaration of the corresponding attribute of the new collection.

EXAMPLE: We continue the example of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ $(𝙸𝙽𝙳𝙴𝚇, 𝚃𝙰𝙱𝙻𝙴, 𝚅𝙰𝙻𝚄𝙴)$ constraint and the derived collection $𝙸𝚃𝙴𝙼 - 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚒𝚗𝚍𝚎𝚡 - 𝚍𝚟𝚊𝚛, 𝚟𝚊𝚕𝚞𝚎 - 𝚍𝚟𝚊𝚛)$ . The pattern $𝚒𝚝𝚎𝚖 (𝚒𝚗𝚍𝚎𝚡 - 𝙸𝙽𝙳𝙴𝚇, 𝚟𝚊𝚕𝚞𝚎 - 𝚅𝙰𝙻𝚄𝙴)$ indicates that:

The $𝚒𝚗𝚍𝚎𝚡$ attribute of the $𝙸𝚃𝙴𝙼$ collection will be generated by using the $𝙸𝙽𝙳𝙴𝚇$ argument of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ constraint. Since $𝙸𝙽𝙳𝙴𝚇$ is a domain variable, it is compatible with the declaration $𝙸𝚃𝙴𝙼 - 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚒𝚗𝚍𝚎𝚡 - 𝚍𝚟𝚊𝚛, 𝚟𝚊𝚕𝚞𝚎 - 𝚍𝚟𝚊𝚛)$ of the new collection.
The $𝚟𝚊𝚕𝚞𝚎$ attribute of the $𝙸𝚃𝙴𝙼$ collection will be generated by using the $𝚅𝙰𝙻𝚄𝙴$ argument of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ constraint. $𝚅𝙰𝙻𝚄𝙴$ is also compatible with the declaration statement of the new collection.

We now describe how we use the pattern for generating the items of a derived collection. We have the following two cases:

If the pattern $o - 𝚒𝚝𝚎𝚖 (𝚊_{1} - v_{1}, 𝚊_{2} - v_{2}, \dots, 𝚊_{n} - v_{n})$ does not contain any direct or indirect reference to an attribute of a collection then we generate a single item for such pattern.In this first case the value of $o$ is irrelevant. In this context the value $v_{i}$ of the attribute $𝚊_{i}$ $(1 \leq i \leq n)$ corresponds to a constant, to an argument of the global constraint or to a new derived collection.
If the pattern $o - 𝚒𝚝𝚎𝚖 (𝚊_{1} - v_{1}, 𝚊_{2} - v_{2}, \dots, 𝚊_{n} - v_{n})$ , where $o$ is one of the comparison operators $=, \neq, <, \geq, >, \leq$ , contains one or several direct or indirect references to an attribute of a collectionThis collection is an argument of the global constraint or corresponds to a newly derived collection. we denote by:
- $𝒟$ the set of indices of the positions corresponding to a direct reference to an attribute of a collection within $𝚒𝚝𝚎𝚖 (𝚊_{1} - v_{1}, 𝚊_{2} - v_{2}, \dots, 𝚊_{n} - v_{n})$ . In this context, let $𝚌_{α_{1}}, 𝚌_{α_{2}}, \dots, 𝚌_{α_{m}}$ and $𝚊_{α_{1}}, 𝚊_{α_{2}}, \dots, 𝚊_{α_{m}}$ respectively denote the corresponding collections and attributes.
- $ℐ$ the set of indices of the positions corresponding to an indirect reference to an attribute of a collection within $𝚒𝚝𝚎𝚖 (𝚊_{1} - v_{1}, 𝚊_{2} - v_{2}, \dots, 𝚊_{n} - v_{n})$ . In this context, let $𝚌_{β_{1}}^{1}, 𝚌_{β_{2}}^{1}, \dots, 𝚌_{β_{p}}^{1}$ , $𝚌_{β_{1}}^{2}, 𝚌_{β_{2}}^{2}, \dots, 𝚌_{β_{p}}^{2}$ and $𝚊_{β_{1}}, 𝚊_{β_{2}}, \dots, 𝚊_{β_{p}}$ respectively denote the corresponding collections, attributes of type collection and attributes.
- Let ${𝑑𝑖𝑟}_{1}, {𝑑𝑖𝑟}_{2}, \dots, {𝑑𝑖𝑟}_{m}$ , ${𝑖𝑛𝑑}_{1}, {𝑖𝑛𝑑}_{2}, \dots, {𝑖𝑛𝑑}_{p}$ and ${𝑖𝑑}_{1}, {𝑖𝑑}_{2}, \dots, {𝑖𝑑}_{m + p}$ respectively denote the indices sorted in increasing order of $𝒟$ , $ℐ$ and $𝒟 \cup ℐ$ .
For each combination of items $𝚌_{α_{1}} [i_{1}], 𝚌_{α_{2}} [i_{2}], \dots, 𝚌_{α_{m}} [i_{m}]$ , $𝚌_{β_{1}}^{1} [j_{1}] . 𝚌_{β_{1}}^{2} [k_{1}], 𝚌_{β_{2}}^{1} [j_{2}] . 𝚌_{β_{2}}^{2} [k_{2}], \dots, 𝚌_{β_{p}}^{1} [j_{p}] . 𝚌_{β_{p}}^{2} [k_{p}]$ such that:

$\{\begin{matrix} i_{1} \in [1, | 𝚌_{α_{1}} |], & i_{2} \in [1, | 𝚌_{α_{2}} |], & \dots, & i_{m} \in [1, | 𝚌_{α_{m}} |] \\ j_{1} \in [1, | 𝚌_{β_{1}}^{1} |], & j_{2} \in [1, | 𝚌_{β_{2}}^{1} |], & \dots, & j_{p} \in [1, | 𝚌_{β_{p}}^{1} |] \\ k_{1} \in [1, | 𝚌_{β_{1}}^{1} [j_{1}] . 𝚌_{β_{1}}^{2} |], & k_{2} \in [1, | 𝚌_{β_{2}}^{1} [j_{2}] . 𝚌_{β_{2}}^{2} |], & \dots, & k_{p} \in [1, | 𝚌_{β_{p}}^{1} [j_{p}] . 𝚌_{β_{p}}^{2} |] \\ {𝑖𝑑}_{1} o {𝑖𝑑}_{2} o \dots o {𝑖𝑑}_{m + p} \end{matrix}$

we generate an item of the new derived collection $〈 𝚊_{1} - w_{1} 𝚊_{2} - w_{2} \dots 𝚊_{n} - w_{n} 〉$ defined by:

$w_{j} (1 \leq j \leq n) = \{\begin{matrix} 𝚌_{α_{r}} [i_{r}] . 𝚊_{α_{r}} & if j \in 𝒟, j = {𝑑𝑖𝑟}_{r} \\ 𝚌_{β_{r}}^{1} [j_{r}] . 𝚌_{β_{r}}^{2} [k_{r}] . 𝚊_{β_{r}} & if j \in ℐ, j = {𝑖𝑛𝑑}_{r} \\ v_{j} & if j \notin 𝒟 \cup ℐ \end{matrix} .$

We illustrate this generation process on a set of examples. Each example is described by providing:

The global constraint and its arguments,
The declaration of the new derived collection,
The pattern used for creating an item of the new collection,
The items generated by applying this pattern to the global constraint,
A comment about the generation process.

We first start with four examples that do not mention any references to an attribute of a collection. A box surrounds an argument of a global constraint that is mentioned in a generated item.

EXAMPLE

$𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃$ :: $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ $(\begin{matrix} 𝙸𝙽𝙳𝙴𝚇 \end{matrix}, 𝚃𝙰𝙱𝙻𝙴, \begin{matrix} 𝚅𝙰𝙻𝚄𝙴 \end{matrix})$
$𝙳𝙴𝚁𝙸𝚅𝙴𝙳 𝙲𝙾𝙻𝙻𝙴𝙲𝚃𝙸𝙾𝙽$ :: $𝙸𝚃𝙴𝙼 - 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚒𝚗𝚍𝚎𝚡 - 𝚍𝚟𝚊𝚛, 𝚟𝚊𝚕𝚞𝚎 - 𝚍𝚟𝚊𝚛)$
$𝙿𝙰𝚃𝚃𝙴𝚁𝙽 (𝚂)$ :: $𝚒𝚝𝚎𝚖 (𝚒𝚗𝚍𝚎𝚡 - 𝙸𝙽𝙳𝙴𝚇, 𝚟𝚊𝚕𝚞𝚎 - 𝚅𝙰𝙻𝚄𝙴)$
$𝙶𝙴𝙽𝙴𝚁𝙰𝚃𝙴𝙳 𝙸𝚃𝙴𝙼 (𝚂)$ :: $〈 𝚒𝚗𝚍𝚎𝚡 - \begin{matrix} 𝙸𝙽𝙳𝙴𝚇 \end{matrix} 𝚟𝚊𝚕𝚞𝚎 - \begin{matrix} 𝚅𝙰𝙻𝚄𝙴 \end{matrix} 〉$

We generate a single item where the two attributes $𝚒𝚗𝚍𝚎𝚡$ and $𝚟𝚊𝚕𝚞𝚎$ respectively take the first argument $𝙸𝙽𝙳𝙴𝚇$ and the third argument $𝚅𝙰𝙻𝚄𝙴$ of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ constraint.

EXAMPLE

$𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃$ :: $𝚕𝚎𝚡_𝚕𝚎𝚜𝚜𝚎𝚚$ $(𝚅𝙴𝙲𝚃𝙾𝚁 1, 𝚅𝙴𝙲𝚃𝙾𝚁 2)$
$𝙳𝙴𝚁𝙸𝚅𝙴𝙳 𝙲𝙾𝙻𝙻𝙴𝙲𝚃𝙸𝙾𝙽$ :: $𝙳𝙴𝚂𝚃𝙸𝙽𝙰𝚃𝙸𝙾𝙽 - 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚒𝚗𝚍𝚎𝚡 - 𝚒𝚗𝚝, 𝚡 - 𝚒𝚗𝚝, 𝚢 - 𝚒𝚗𝚝)$
$𝙿𝙰𝚃𝚃𝙴𝚁𝙽 (𝚂)$ :: $𝚒𝚝𝚎𝚖 (𝚒𝚗𝚍𝚎𝚡 - 0, 𝚡 - 0, 𝚢 - 0)$
$𝙶𝙴𝙽𝙴𝚁𝙰𝚃𝙴𝙳 𝙸𝚃𝙴𝙼 (𝚂)$ :: $〈 𝚒𝚗𝚍𝚎𝚡 - 0 𝚡 - 0 𝚢 - 0 〉$

We generate a single item where the three attributes $𝚒𝚗𝚍𝚎𝚡$ , $𝚡$ and $𝚢$ take value 0.

EXAMPLE

$𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃$ :: $𝚒𝚗_𝚛𝚎𝚕𝚊𝚝𝚒𝚘𝚗$ $(\begin{matrix} 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 \end{matrix}, 𝚃𝚄𝙿𝙻𝙴𝚂_𝙾𝙵_𝚅𝙰𝙻𝚂)$
$𝙳𝙴𝚁𝙸𝚅𝙴𝙳 𝙲𝙾𝙻𝙻𝙴𝙲𝚃𝙸𝙾𝙽$ :: $𝚃𝚄𝙿𝙻𝙴𝚂_𝙾𝙵_𝚅𝙰𝚁𝚂 - 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚎𝚌 - 𝚃𝚄𝙿𝙻𝙴_𝙾𝙵_𝚅𝙰𝚁𝚂)$
$𝙿𝙰𝚃𝚃𝙴𝚁𝙽 (𝚂)$ :: $𝚒𝚝𝚎𝚖 (𝚟𝚎𝚌 - 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$
$𝙶𝙴𝙽𝙴𝚁𝙰𝚃𝙴𝙳 𝙸𝚃𝙴𝙼 (𝚂)$ :: $〈 𝚟𝚎𝚌 - \begin{matrix} 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 \end{matrix} 〉$

We generate a single item where the unique attribute $𝚟𝚎𝚌$ takes the first argument of the $𝚒𝚗_𝚛𝚎𝚕𝚊𝚝𝚒𝚘𝚗$ constraint as its value.

EXAMPLE

$𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃$ :: $𝚍𝚘𝚖𝚊𝚒𝚗_𝚌𝚘𝚗𝚜𝚝𝚛𝚊𝚒𝚗𝚝$ $(\begin{matrix} 𝚅𝙰𝚁 \end{matrix}, 𝚅𝙰𝙻𝚄𝙴𝚂)$
$𝙳𝙴𝚁𝙸𝚅𝙴𝙳 𝙲𝙾𝙻𝙻𝙴𝙲𝚃𝙸𝙾𝙽$ :: $𝚅𝙰𝙻𝚄𝙴 - 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 01 - 𝚒𝚗𝚝, 𝚟𝚊𝚕𝚞𝚎 - 𝚍𝚟𝚊𝚛)$
$𝙿𝙰𝚃𝚃𝙴𝚁𝙽 (𝚂)$ :: $𝚒𝚝𝚎𝚖 (𝚟𝚊𝚛 01 - 1, 𝚟𝚊𝚕𝚞𝚎 - 𝚅𝙰𝚁)$
$𝙶𝙴𝙽𝙴𝚁𝙰𝚃𝙴𝙳 𝙸𝚃𝙴𝙼 (𝚂)$ :: $〈 𝚟𝚊𝚛 01 - 1 𝚟𝚊𝚕𝚞𝚎 - \begin{matrix} 𝚅𝙰𝚁 \end{matrix} 〉$

We generate a single item where the two attributes $𝚟𝚊𝚛 01$ and $𝚟𝚊𝚕𝚞𝚎$ respectively take value 1 and the first argument of the $𝚍𝚘𝚖𝚊𝚒𝚗_𝚌𝚘𝚗𝚜𝚝𝚛𝚊𝚒𝚗𝚝$ constraint.

We continue with three examples that mention one or several direct references to an attribute of some collections. We now need to explicitly give the items of these collections in order to generate the items of the derived collection.

EXAMPLE

$𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃$ :

$𝚕𝚎𝚡_𝚕𝚎𝚜𝚜𝚎𝚚$ $(\begin{matrix} 𝚅𝙴𝙲𝚃𝙾𝚁 1 \end{matrix}, \begin{matrix} 𝚅𝙴𝙲𝚃𝙾𝚁 2 \end{matrix})$

$𝚅𝙴𝙲𝚃𝙾𝚁 1$ :

$〈 𝚟𝚊𝚛 - 5, 𝚟𝚊𝚛 - 2, 𝚟𝚊𝚛 - 3, 𝚟𝚊𝚛 - 1 〉$

$𝚅𝙴𝙲𝚃𝙾𝚁 2$ :

$〈 𝚟𝚊𝚛 - 5, 𝚟𝚊𝚛 - 2, 𝚟𝚊𝚛 - 6, 𝚟𝚊𝚛 - 2 〉$

$𝙳𝙴𝚁𝙸𝚅𝙴𝙳 𝙲𝙾𝙻𝙻𝙴𝙲𝚃𝙸𝙾𝙽$ :

$𝙲𝙾𝙼𝙿𝙾𝙽𝙴𝙽𝚃𝚂 - 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚒𝚗𝚍𝚎𝚡 - 𝚒𝚗𝚝,$

$𝚡 - 𝚍𝚟𝚊𝚛, 𝚢 - 𝚍𝚟𝚊𝚛)$

$𝙿𝙰𝚃𝚃𝙴𝚁𝙽 (𝚂)$ :

$𝚒𝚝𝚎𝚖 (𝚒𝚗𝚍𝚎𝚡 - 𝚅𝙴𝙲𝚃𝙾𝚁 1 . 𝚔𝚎𝚢$ As defined in Section 2.2.2 on page 2.2.2, $𝚔𝚎𝚢$ is an implicit attribute corresponding to the position of an item within a collection. $,$

$𝚡 - 𝚅𝙴𝙲𝚃𝙾𝚁 1 . 𝚟𝚊𝚛, 𝚢 - 𝚅𝙴𝙲𝚃𝙾𝚁 2 . 𝚟𝚊𝚛)$

$𝙶𝙴𝙽𝙴𝚁𝙰𝚃𝙴𝙳 𝙸𝚃𝙴𝙼 (𝚂)$ :

$〈 𝚒𝚗𝚍𝚎𝚡 - 1 𝚡 - 5 𝚢 - 5, 𝚒𝚗𝚍𝚎𝚡 - 2 𝚡 - 2 𝚢 - 2,$

$𝚒𝚗𝚍𝚎𝚡 - 3 𝚡 - 3 𝚢 - 6, 𝚒𝚗𝚍𝚎𝚡 - 4 𝚡 - 1 𝚢 - 2 〉$

The pattern mentions three references $𝚅𝙴𝙲𝚃𝙾𝚁 1 . 𝚔𝚎𝚢$ , $𝚅𝙴𝙲𝚃𝙾𝚁 1 . 𝚟𝚊𝚛$ and $𝚅𝙴𝙲𝚃𝙾𝚁 2 . 𝚟𝚊𝚛$ to the collections $𝚅𝙴𝙲𝚃𝙾𝚁 1$ and $𝚅𝙴𝙲𝚃𝙾𝚁 2$ used in the arguments of the $𝚕𝚎𝚡_𝚕𝚎𝚜𝚜𝚎𝚚$ constraint. $\forall i_{1} \in [1, | 𝚅𝙴𝙲𝚃𝙾𝚁 1 |], \forall i_{2} \in [1, | 𝚅𝙴𝙲𝚃𝙾𝚁 2 |]$ such that $i_{1} = i_{2}$ We use an equality since this is the default value of the comparison operator $o$ when we do not use a pattern of the form $o - 𝚒𝚝𝚎𝚖 (\dots)$ . we generate an item $𝚒𝚗𝚍𝚎𝚡 - v_{1} 𝚡 - v_{2} 𝚢 - v_{3}$ where:

$v_{1} = i_{1}, v_{2} = 𝚅𝙴𝙲𝚃𝙾𝚁 1 [i_{1}] . 𝚟𝚊𝚛, v_{3} = 𝚅𝙴𝙲𝚃𝙾𝚁 2 [i_{1}] . 𝚟𝚊𝚛 .$

This leads to the four items listed in the $𝙶𝙴𝙽𝙴𝚁𝙰𝚃𝙴𝙳 𝙸𝚃𝙴𝙼 (𝚂)$ field.

EXAMPLE

$𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃$ :

$𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜$ $(\begin{matrix} 𝚃𝙰𝚂𝙺𝚂 \end{matrix}, 𝙼𝙰𝙲𝙷𝙸𝙽𝙴𝚂, 𝙲𝚃𝚁)$

$𝚃𝙰𝚂𝙺𝚂$ :

$〈 𝚖𝚊𝚌𝚑𝚒𝚗𝚎 - 1 𝚘𝚛𝚒𝚐𝚒𝚗 - 1 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 4 𝚎𝚗𝚍 - 5 𝚑𝚎𝚒𝚐𝚑𝚝 - 1,$

$𝚖𝚊𝚌𝚑𝚒𝚗𝚎 - 1 𝚘𝚛𝚒𝚐𝚒𝚗 - 4 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 2 𝚎𝚗𝚍 - 6 𝚑𝚎𝚒𝚐𝚑𝚝 - 3,$

$𝚖𝚊𝚌𝚑𝚒𝚗𝚎 - 1 𝚘𝚛𝚒𝚐𝚒𝚗 - 2 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 3 𝚎𝚗𝚍 - 5 𝚑𝚎𝚒𝚐𝚑𝚝 - 2,$

$𝚖𝚊𝚌𝚑𝚒𝚗𝚎 - 2 𝚘𝚛𝚒𝚐𝚒𝚗 - 5 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 2 𝚎𝚗𝚍 - 7 𝚑𝚎𝚒𝚐𝚑𝚝 - 2 〉$

$𝙳𝙴𝚁𝙸𝚅𝙴𝙳 𝙲𝙾𝙻𝙻𝙴𝙲𝚃𝙸𝙾𝙽$ :

$𝚃𝙸𝙼𝙴_𝙿𝙾𝙸𝙽𝚃𝚂 - 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚒𝚍𝚖 - 𝚒𝚗𝚝,$

$𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 𝚍𝚟𝚊𝚛, 𝚙𝚘𝚒𝚗𝚝 - 𝚍𝚟𝚊𝚛)$

$𝙿𝙰𝚃𝚃𝙴𝚁𝙽 (𝚂)$ :

$𝚒𝚝𝚎𝚖 (𝚒𝚍𝚖 - 𝚃𝙰𝚂𝙺𝚂 . 𝚖𝚊𝚌𝚑𝚒𝚗𝚎,$

$𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 𝚃𝙰𝚂𝙺𝚂 . 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗, 𝚙𝚘𝚒𝚗𝚝 - 𝚃𝙰𝚂𝙺𝚂 . 𝚘𝚛𝚒𝚐𝚒𝚗)$

$𝚒𝚝𝚎𝚖 (𝚒𝚍𝚖 - 𝚃𝙰𝚂𝙺𝚂 . 𝚖𝚊𝚌𝚑𝚒𝚗𝚎,$

$𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 𝚃𝙰𝚂𝙺𝚂 . 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗, 𝚙𝚘𝚒𝚗𝚝 - 𝚃𝙰𝚂𝙺𝚂 . 𝚎𝚗𝚍)$

$𝙶𝙴𝙽𝙴𝚁𝙰𝚃𝙴𝙳 𝙸𝚃𝙴𝙼 (𝚂)$ :

$〈 𝚒𝚍𝚖 - 1 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 4 𝚙𝚘𝚒𝚗𝚝 - 1,$

$𝚒𝚍𝚖 - 1 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 2 𝚙𝚘𝚒𝚗𝚝 - 4,$

$𝚒𝚍𝚖 - 1 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 3 𝚙𝚘𝚒𝚗𝚝 - 2,$

$𝚒𝚍𝚖 - 2 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 2 𝚙𝚘𝚒𝚗𝚝 - 5,$

$𝚒𝚍𝚖 - 1 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 4 𝚙𝚘𝚒𝚗𝚝 - 5,$

$𝚒𝚍𝚖 - 1 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 2 𝚙𝚘𝚒𝚗𝚝 - 6,$

$𝚒𝚍𝚖 - 1 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 3 𝚙𝚘𝚒𝚗𝚝 - 5,$

$𝚒𝚍𝚖 - 2 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 2 𝚙𝚘𝚒𝚗𝚝 - 7 〉$

The two patterns mention the references $𝚃𝙰𝚂𝙺𝚂 . 𝚖𝚊𝚌𝚑𝚒𝚗𝚎$ , $𝚃𝙰𝚂𝙺𝚂 . 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗$ , $𝚃𝙰𝚂𝙺𝚂 . 𝚘𝚛𝚒𝚐𝚒𝚗$ and $𝚃𝙰𝚂𝙺𝚂 . 𝚎𝚗𝚍$ of the $𝚃𝙰𝚂𝙺𝚂$ collection used in the arguments of the $𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜$ constraint. $\forall i \in [1, | 𝚃𝙰𝚂𝙺𝚂 |]$ , we generate two items $𝚒𝚍𝚖 - u_{1} 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - u_{2} 𝚙𝚘𝚒𝚗𝚝 - u_{3}$ , $𝚒𝚍𝚖 - v_{1} 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - v_{2} 𝚙𝚘𝚒𝚗𝚝 - v_{3}$ where:

$u_{1} = 𝚃𝙰𝚂𝙺𝚂 [i] . 𝚖𝚊𝚌𝚑𝚒𝚗𝚎, u_{2} = 𝚃𝙰𝚂𝙺𝚂 [i] . 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗, u_{3} = 𝚃𝙰𝚂𝙺𝚂 [i] . 𝚘𝚛𝚒𝚐𝚒𝚗,$

$v_{1} = 𝚃𝙰𝚂𝙺𝚂 [i] . 𝚖𝚊𝚌𝚑𝚒𝚗𝚎, v_{2} = 𝚃𝙰𝚂𝙺𝚂 [i] . 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗, v_{3} = 𝚃𝙰𝚂𝙺𝚂 [i] . 𝚎𝚗𝚍$ .

This leads to the eight items listed in the $𝙶𝙴𝙽𝙴𝚁𝙰𝚃𝙴𝙳 𝙸𝚃𝙴𝙼 (𝚂)$ field.

EXAMPLE

$𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃$ :

$𝚐𝚘𝚕𝚘𝚖𝚋$ $(\begin{matrix} 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 \end{matrix})$

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ :

$〈 𝚟𝚊𝚛 - 0, 𝚟𝚊𝚛 - 1, 𝚟𝚊𝚛 - 4, 𝚟𝚊𝚛 - 6 〉$

$𝙳𝙴𝚁𝙸𝚅𝙴𝙳 𝙲𝙾𝙻𝙻𝙴𝙲𝚃𝙸𝙾𝙽$ :

$𝙿𝙰𝙸𝚁𝚂 - 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚡 - 𝚍𝚟𝚊𝚛, 𝚢 - 𝚍𝚟𝚊𝚛)$

$𝙿𝙰𝚃𝚃𝙴𝚁𝙽 (𝚂)$ :

$> - 𝚒𝚝𝚎𝚖 (𝚡 - 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛, 𝚢 - 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛)$

$𝙶𝙴𝙽𝙴𝚁𝙰𝚃𝙴𝙳 𝙸𝚃𝙴𝙼 (𝚂)$ :

$〈 𝚡 - 1 𝚢 - 0,$

$𝚡 - 4 𝚢 - 0, 𝚡 - 4 𝚢 - 1,$

$𝚡 - 6 𝚢 - 0, 𝚡 - 6 𝚢 - 1, 𝚡 - 6 𝚢 - 4 〉$

The pattern mentions two references $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ and $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ to the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection used in the arguments of the $𝚐𝚘𝚕𝚘𝚖𝚋$ constraint. $\forall i_{1} \in [1, | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |]$ , $\forall i_{2} \in [1, | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |]$ such that $i_{1} > i_{2}$ We use the comparison operator $>$ since we have a pattern of the form $> - 𝚒𝚝𝚎𝚖 (\dots)$ . we generate the item $𝚡 - u_{1} 𝚢 - u_{2}$ where:

$u_{1} = 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 [i_{1}] . 𝚟𝚊𝚛, u_{2} = 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 [i_{2}] . 𝚟𝚊𝚛$ .

This leads to the six items listed in the $𝙶𝙴𝙽𝙴𝚁𝙰𝚃𝙴𝙳 𝙸𝚃𝙴𝙼 (𝚂)$ field.

We finish with an example that mentions an indirect reference to an attribute of a collection.

EXAMPLE

$𝙲𝙾𝙽𝚂𝚃𝚁𝙰𝙸𝙽𝚃$ :

$𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎_𝚌𝚘𝚗𝚟𝚎𝚡$ $(\begin{matrix} 𝚃𝙰𝚂𝙺𝚂 \end{matrix}, 𝙻𝙸𝙼𝙸𝚃)$

$𝚃𝙰𝚂𝙺𝚂$ :

$〈 𝚙𝚘𝚒𝚗𝚝𝚜 - 〈 𝚟𝚊𝚛 - 2, 𝚟𝚊𝚛 - 1, 𝚟𝚊𝚛 - 5 〉 𝚑𝚎𝚒𝚐𝚑𝚝 - 1,$

$𝚙𝚘𝚒𝚗𝚝𝚜 - 〈 𝚟𝚊𝚛 - 4, 𝚟𝚊𝚛 - 5, 𝚟𝚊𝚛 - 7 〉 𝚑𝚎𝚒𝚐𝚑𝚝 - 2,$

$𝚙𝚘𝚒𝚗𝚝𝚜 - 〈 𝚟𝚊𝚛 - 14, 𝚟𝚊𝚛 - 15 〉 𝚑𝚎𝚒𝚐𝚑𝚝 - 2 〉$

$𝙳𝙴𝚁𝙸𝚅𝙴𝙳 𝙲𝙾𝙻𝙻𝙴𝙲𝚃𝙸𝙾𝙽$ :

$𝙸𝙽𝚂𝚃𝙰𝙽𝚃𝚂 - 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚒𝚗𝚜𝚝𝚊𝚗𝚝 - 𝚒𝚗𝚝)$

$𝙿𝙰𝚃𝚃𝙴𝚁𝙽 (𝚂)$ :

$𝚒𝚝𝚎𝚖 (𝚒𝚗𝚜𝚝𝚊𝚗𝚝 - 𝚃𝙰𝚂𝙺𝚂 . 𝚙𝚘𝚒𝚗𝚝𝚜 . 𝚟𝚊𝚛)$

$𝙶𝙴𝙽𝙴𝚁𝙰𝚃𝙴𝙳 𝙸𝚃𝙴𝙼 (𝚂)$ :

$〈 𝚒𝚗𝚜𝚝𝚊𝚗𝚝 - 2, 𝚒𝚗𝚜𝚝𝚊𝚗𝚝 - 1, 𝚒𝚗𝚜𝚝𝚊𝚗𝚝 - 5, 𝚒𝚗𝚜𝚝𝚊𝚗𝚝 - 4,$

$𝚒𝚗𝚜𝚝𝚊𝚗𝚝 - 5, 𝚒𝚗𝚜𝚝𝚊𝚗𝚝 - 7, 𝚒𝚗𝚜𝚝𝚊𝚗𝚝 - 14, 𝚒𝚗𝚜𝚝𝚊𝚗𝚝 - 15 〉$

The pattern mentions the indirect reference $𝚃𝙰𝚂𝙺𝚂 . 𝚙𝚘𝚒𝚗𝚝𝚜 . 𝚟𝚊𝚛$ of the $𝚃𝙰𝚂𝙺𝚂$ collection used in the arguments of the $𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎_𝚌𝚘𝚗𝚟𝚎𝚡$ constraint. $\forall i \in [1, | 𝚃𝙰𝚂𝙺𝚂 |]$ , $\forall j \in [1, | 𝚃𝙰𝚂𝙺𝚂 [i] . 𝚙𝚘𝚒𝚗𝚝𝚜 |]$ we generate the item $𝚒𝚗𝚜𝚝𝚊𝚗𝚝 - u_{i j}$ where:

$u_{i j} = 𝚃𝙰𝚂𝙺𝚂 [i] . 𝚙𝚘𝚒𝚗𝚝𝚜 [j]$ .

This leads to the eight items listed in the $𝙶𝙴𝙽𝙴𝚁𝙰𝚃𝙴𝙳 𝙸𝚃𝙴𝙼 (𝚂)$ field.

Global Constraint Catalog

2. Describing Global Constraints

2.3.2.1. Collection generators