Global Constraint Catalog

2.2.5. Describing symmetries between arguments

Given a satisfied ground instance of a global constraint $𝚌𝚘𝚗𝚜𝚝𝚛𝚊𝚒𝚗𝚝$ , it is often the case that the constraint is still satisfied [CohenJeavonsJeffersonPetrieSmith06], [FlenerPearsonSellmannVanHentenryckAgren09] if we permute:

Some of its arguments.

E.g., consider the disequality constraint $𝚗𝚎𝚚$ $(𝚇, 𝚈)$ , which forces $𝚇$ being assigned an integer value that is different from $𝚈$ . Given the solution $𝚗𝚎𝚚$ $(3, 5)$ we can swap both arguments and still get a solution (i.e., $𝚗𝚎𝚚$ $(5, 3)$ ).
Items of some collections that are passed as one of its arguments.

E.g., consider the $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ $(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$ constraint, which imposes all variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ being assigned a distinct integer value. Given the solution $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ $(〈 5, 1, 9, 3 〉)$ we can swap any pair of items and still get a solution. For instance, if we swap the first and fourth items we still get a solution (i.e., $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ $(〈 3, 1, 9, 5 〉)$ ).
Attributes of some items of some of its collections.

E.g., given a collection of pairs $𝙿𝙰𝙸𝚁𝚂$ , where each pair has two attributes $𝚡$ and $𝚢$ , the $𝚗𝚙𝚊𝚒𝚛$ $(𝙽, 𝙿𝙰𝙸𝚁𝚂)$ constraint forces $𝙽$ being the number of distinct pairs in $𝙿𝙰𝙸𝚁𝚂$ . Given the solution $𝚗𝚙𝚊𝚒𝚛$ $(3, 〈 𝚡 - 3 𝚢 - 1, 𝚡 - 1 𝚢 - 5, 𝚡 - 3 𝚢 - 1, 𝚡 - 1 𝚢 - 5, 𝚡 - 1 𝚢 - 3 〉)$ we can interchange attributes $𝚡$ and $𝚢$ and still get a solution (i.e., $𝚗𝚙𝚊𝚒𝚛$ $(3, 〈 𝚡 - 1 𝚢 - 3, 𝚡 - 5 𝚢 - 1, 𝚡 - 1 𝚢 - 3, 𝚡 - 5 𝚢 - 1, 𝚡 - 3 𝚢 - 1 〉)$ ).
A pair of values with respect to an attribute of some of its collections.

E.g., consider the $𝚋𝚒𝚗_𝚙𝚊𝚌𝚔𝚒𝚗𝚐$ constraint, which assigns items to bins in such a way that the total weight of the items in each bin does not exceed an overall fixed capacity. Each item has a $𝚋𝚒𝚗$ and a $𝚠𝚎𝚒𝚐𝚑𝚝$ attributes, which respectively give the bin to which the item will be assigned, and the weight of the item. Given the solution $𝚋𝚒𝚗_𝚙𝚊𝚌𝚔𝚒𝚗𝚐$ $(5, 〈 𝚋𝚒𝚗 - 3 𝚠𝚎𝚒𝚐𝚑𝚝 - 4, 𝚋𝚒𝚗 - 1 𝚠𝚎𝚒𝚐𝚑𝚝 - 3, 𝚋𝚒𝚗 - 3 𝚠𝚎𝚒𝚐𝚑𝚝 - 1 〉)$ , we can interchange all occurrences of value 3 with all occurrences of value 1 with respect to the $𝚋𝚒𝚗$ attribute. After this swap of values we get the new solution $𝚋𝚒𝚗_𝚙𝚊𝚌𝚔𝚒𝚗𝚐$ $(5, 〈 𝚋𝚒𝚗 - 1 𝚠𝚎𝚒𝚐𝚑𝚝 - 4, 𝚋𝚒𝚗 - 3 𝚠𝚎𝚒𝚐𝚑𝚝 - 3, 𝚋𝚒𝚗 - 1 𝚠𝚎𝚒𝚐𝚑𝚝 - 1 〉)$ . This simply consists of swapping the content of two bins. Since all bins have the same capacity we still get a solution.

We provide the following moves, where each move is described by (1) an explicit fact (i.e., a meta-data), (2) a textual explanation, and (3) several concrete examples:

$𝚊𝚛𝚐𝚜 (𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽)$ denotes the fact that we swap the arguments of a constraint with respect to a given permutation. Arguments which are exchanged must have the same type under the hypothesis that they are ground (i.e., for instance the basic data types $𝚒𝚗𝚝$ and $𝚍𝚟𝚊𝚛$ , which respectively denote an integer value and a domain variable can be exchanged since a ground domain variable corresponds to an integer value). The permutation $𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽$ is described by using standard notation, that is by providing the different cycles of the permutation.

EXAMPLE 1: As a first example where we can swap two arguments, consider the $𝚎𝚚_𝚌𝚜𝚝$ $(𝚅𝙰𝚁 1, 𝚅𝙰𝚁 2, 𝙲𝚂𝚃 2)$ constraint which, given two domain variables $𝚅𝙰𝚁 1$ , $𝚅𝙰𝚁 2$ and an integer value $𝙲𝚂𝚃 2$ , forces the condition $𝚅𝙰𝚁 1 = 𝚅𝙰𝚁 2 + 𝙲𝚂𝚃 2$ . Within the electronic catalogue this is represented by the following meta-data, $𝚊𝚛𝚐𝚜 ([[𝚅𝙰𝚁 1], [𝚅𝙰𝚁 2, 𝙲𝚂𝚃 2]])$ , to which corresponds the following textual form:

arguments are permutable w.r.t. permutation $(𝚅𝙰𝚁 1)$ $(𝚅𝙰𝚁 2, 𝙲𝚂𝚃 2)$ .

Note that, even though arguments $𝚅𝙰𝚁 2$ and $𝙲𝚂𝚃 2$ do not have the same type (i.e., $𝚅𝙰𝚁 2$ is a domain variable, while $𝙲𝚂𝚃 2$ is an integer value), both arguments can be exchanged since we consider the ground case. For instance, since $𝚎𝚚_𝚌𝚜𝚝$ $(8, 2, 6)$ is satisfied, $𝚎𝚚_𝚌𝚜𝚝$ $(8, 6, 2)$ is also satisfied.
EXAMPLE 2: As a second example where we can swap several arguments, consider the $𝚌𝚘𝚖𝚖𝚘𝚗$ $(𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1, 𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2)$ constraint which, given two domain variables $𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1$ , $𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2$ and two collections of domain variables $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ , $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ , forces the following two conditions:
- $𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1$ is the number of variables of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ assigned a value in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ .
- $𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2$ is the number of variables of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ assigned a value in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ .
Within the electronic catalogue this is represented by the following meta-data, $𝚊𝚛𝚐𝚜 ([[𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1, 𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2], [𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2]])$ , to which corresponds the following textual form:

arguments are permutable w.r.t. permutation $(𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1, 𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2)$

$(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2)$ .

For instance, since $𝚌𝚘𝚖𝚖𝚘𝚗$ $(3, 4, 〈 1, 9, 1, 5 〉, 〈 2, 1, 9, 9, 6, 9 〉)$ is satisfied, $𝚌𝚘𝚖𝚖𝚘𝚗$ $(4, 3, 〈 2, 1, 9, 9, 6, 9 〉, 〈 1, 9, 1, 5 〉)$ is also satisfied.
$𝚒𝚝𝚎𝚖𝚜 (𝙲𝙾𝙻𝙻𝙴𝙲𝚃𝙸𝙾𝙽, 𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽𝚂)$ denotes the fact that we can permute the items of the collection $𝙲𝙾𝙻𝙻𝙴𝙲𝚃𝙸𝙾𝙽$ with respect to a permutation belonging to a given set of permutations $𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽𝚂$ :
- $𝙲𝙾𝙻𝙻𝙴𝙲𝚃𝙸𝙾𝙽$ stands for one of the following:
  1. An argument $𝙰𝚁𝙶$ of the global constraint that corresponds to a $𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗$ of items.
  2. A term $𝙰𝚁𝙶 . 𝚊𝚝𝚝𝚛$ , where $𝚊𝚝𝚝𝚛$ is an attribute of a $𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗$ of items that is an argument $𝙰𝚁𝙶$ of the global constraint; in addition, the type of $𝚊𝚝𝚝𝚛$ is itself a collection. Given a collection $𝙰𝚁𝙶$ of $m$ items $〈 𝙰𝚁𝙶 [1], 𝙰𝚁𝙶 [2], \dots, 𝙰𝚁𝙶 [m] 〉$ , a permutation of $𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽𝚂$ , not necessarily the same, is applied on the items of a subset of the set of collections ${𝙰𝚁𝙶 [1] . 𝚊𝚝𝚝𝚛, 𝙰𝚁𝙶 [2] . 𝚊𝚝𝚝𝚛, \dots, 𝙰𝚁𝙶 [m] . 𝚊𝚝𝚝𝚛}$ .
- $𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽𝚂$ represents a set of permutations. It can take one of the following values:
  1. $𝚊𝚕𝚕$ stands for all possible permutations. Note that this case is a little artificial since it does not really correspond to a symmetry of the constraint, but rather to the use of a collection for representing a set of variables. But, to our best knowledge in 2010, concrete solvers do also not use sets of variables but rather collections, lists or arrays of variables.
  2. $𝚛𝚎𝚟𝚎𝚛𝚜𝚎$ stands for the set that only contains the permutation that maps the sequence $e_{1}, e_{2}, \dots, e_{n}$ to $e_{n}, e_{n - 1}, \dots, e_{1}$ .
  3. $𝚜𝚑𝚒𝚏𝚝$ stands for the set that only contains the permutation that maps the sequence $e_{1}, e_{2}, \dots, e_{n}$ to $e_{n}, e_{1}, \dots, e_{n - 1}$ .
EXAMPLE 1: As a first example, consider the $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ $(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$ constraint, which has a single argument corresponding to a collection of variables which must all be assigned distinct values. Within the electronic catalogue this is represented by the following meta-data, $𝚒𝚝𝚎𝚖𝚜 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚊𝚕𝚕)$ , to which corresponds the following textual form:

items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ are permutable.

For instance, since $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ $(〈 1, 4, 9 〉)$ is satisfied, all permutations of $〈 1, 4, 9 〉$ (i.e., $〈 1, 4, 9 〉$ , $〈 1, 9, 4 〉$ , $〈 4, 1, 9 〉$ , $〈 4, 9, 1 〉$ , $〈 9, 1, 4 〉$ , $〈 9, 4, 1 〉$ ) correspond to valid solutions to the $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ constraint.
EXAMPLE 2: As a second example, consider the $𝚔_𝚜𝚊𝚖𝚎$ $(𝚂𝙴𝚃𝚂)$ constraint, which has a single argument corresponding to a collection of sets, where each set is a collection of domain variables that must be assigned the same set of values (i.e., $𝚔_𝚜𝚊𝚖𝚎$ forces an equality between multisets). The argument $𝚂𝙴𝚃𝚂$ is a collection, where each item consists of a single $𝚜𝚎𝚝$ attribute. The type of a $𝚜𝚎𝚝$ attribute is a collection of domain variables. Within the electronic catalogue this is represented by the following meta-data, $𝚒𝚝𝚎𝚖𝚜 (𝚂𝙴𝚃𝚂 . 𝚜𝚎𝚝, 𝚊𝚕𝚕)$ , to which corresponds the following textual form:

items of $𝚂𝙴𝚃𝚂 . 𝚜𝚎𝚝$ are permutable.

For instance, since $𝚔_𝚜𝚊𝚖𝚎$ $(〈 𝚜𝚎𝚝 - 〈 1, 4, 4 〉, 𝚜𝚎𝚝 - 〈 4, 4, 1 〉, 𝚜𝚎𝚝 - 〈 1, 4, 4 〉 〉)$ is satisfied, it is also satisfied for all permutations of the elements of its second set $〈 4, 4, 1 〉$ , i.e.:
- $𝚔_𝚜𝚊𝚖𝚎$ $(〈 𝚜𝚎𝚝 - 〈 1, 4, 4 〉, 𝚜𝚎𝚝 - 〈 1, 4, 4 〉, 𝚜𝚎𝚝 - 〈 1, 4, 4 〉 〉)$ ,
- $𝚔_𝚜𝚊𝚖𝚎$ $(〈 𝚜𝚎𝚝 - 〈 1, 4, 4 〉, 𝚜𝚎𝚝 - 〈 4, 1, 4 〉, 𝚜𝚎𝚝 - 〈 1, 4, 4 〉 〉)$ ,
- $𝚔_𝚜𝚊𝚖𝚎$ $(〈 𝚜𝚎𝚝 - 〈 1, 4, 4 〉, 𝚜𝚎𝚝 - 〈 4, 4, 1 〉, 𝚜𝚎𝚝 - 〈 1, 4, 4 〉 〉)$ .
$𝚒𝚝𝚎𝚖𝚜_𝚜𝚢𝚗𝚌 (𝙲𝙾𝙻𝙻𝙴𝙲𝚃𝙸𝙾𝙽𝚂, 𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽𝚂)$ denotes the fact that we can permute the items of several collections $𝙲𝙾𝙻𝙻𝙴𝙲𝚃𝙸𝙾𝙽𝚂$ with respect to a permutation belonging to a given set of permutations $𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽𝚂$ in such a way that one and the same permutation is used on all collections (i.e., therefore the keyword $𝚒𝚝𝚎𝚖𝚜_𝚜𝚢𝚗𝚌$ which stands for items synchronisation):
- $𝙲𝙾𝙻𝙻𝙴𝙲𝚃𝙸𝙾𝙽𝚂$ stands for a non-empty list of terms of the form $𝙰𝚁𝙶$ or $𝙰𝚁𝙶 . 𝚊𝚝𝚝𝚛$ , where $𝙰𝚁𝙶$ is an argument of the global constraint that corresponds to a collection, and $𝚊𝚝𝚝𝚛$ is an attribute of $𝙰𝚁𝙶$ such that its type is itself a collection. In addition, we also have the following restrictions:
  1. If $𝙲𝙾𝙻𝙻𝙴𝙲𝚃𝙸𝙾𝙽𝚂$ contains a single element then this element has the form $𝙰𝚁𝙶 . 𝚊𝚝𝚝𝚛$ . This is done to allow to designate more than a single collection.
  2. All collections designated by $𝙲𝙾𝙻𝙻𝙴𝙲𝚃𝙸𝙾𝙽𝚂$ have the same type as well as the same number of items.
  The same permutation of $𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽𝚂$ is applied on the items of the different collections referenced by $𝙲𝙾𝙻𝙻𝙴𝙲𝚃𝙸𝙾𝙽𝚂$ .
- As for the symmetry keyword $𝚒𝚝𝚎𝚖𝚜$ , $𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽𝚂$ represents a set of permutations. It can take the same set of values as before, namely:
  1. $𝚊𝚕𝚕$ stands for all possible permutations.
  2. $𝚛𝚎𝚟𝚎𝚛𝚜𝚎$ stands for the set that only contains the permutation that maps the sequence $e_{1}, e_{2}, \dots, e_{n}$ to $e_{n}, e_{n - 1}, \dots, e_{1}$ .
  3. $𝚜𝚑𝚒𝚏𝚝$ stands for the set that only contains the permutation that maps the sequence $e_{1}, e_{2}, \dots, e_{n}$ to $e_{n}, e_{1}, \dots, e_{n - 1}$ .
EXAMPLE 1: As a first example, consider the $𝚌𝚘𝚗𝚜𝚎𝚌𝚞𝚝𝚒𝚟𝚎_𝚐𝚛𝚘𝚞𝚙𝚜_𝚘𝚏_𝚘𝚗𝚎𝚜$ $(𝙶𝚁𝙾𝚄𝙿_𝚂𝙸𝚉𝙴𝚂,$ $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$ constraint, which has two arguments $𝙶𝚁𝙾𝚄𝙿_𝚂𝙸𝚉𝙴𝚂$ and $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ respectively corresponding to a collection of positive integers and to a collection of 0-1 domain variables. The constraint imposes that the $m$ successive maximum groups of consecutive ones of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ have sizes $𝙶𝚁𝙾𝚄𝙿_𝚂𝙸𝚉𝙴𝚂 [1] . 𝚗𝚋$ , $𝙶𝚁𝙾𝚄𝙿_𝚂𝙸𝚉𝙴𝚂 [2] . 𝚗𝚋$ , $\dots$ , $𝙶𝚁𝙾𝚄𝙿_𝚂𝙸𝚉𝙴𝚂 [m] . 𝚗𝚋$ . Note that, if we reverse the items of both $𝙶𝚁𝙾𝚄𝙿_𝚂𝙸𝚉𝙴𝚂$ and $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ , we still have a solution. Within the electronic catalogue this is represented by the following meta-data, $𝚒𝚝𝚎𝚖𝚜_𝚜𝚢𝚗𝚌 ([𝙶𝚁𝙾𝚄𝙿_𝚂𝙸𝚉𝙴𝚂, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂], 𝚛𝚎𝚟𝚎𝚛𝚜𝚎)$ , to which corresponds the following textual form:

items of $𝙶𝚁𝙾𝚄𝙿_𝚂𝙸𝚉𝙴𝚂$ and $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ are simultaneously reversible.

For instance, since $𝚌𝚘𝚗𝚜𝚎𝚌𝚞𝚝𝚒𝚟𝚎_𝚐𝚛𝚘𝚞𝚙𝚜_𝚘𝚏_𝚘𝚗𝚎𝚜$ $(〈 2, 1 〉, 〈 1, 1, 0, 0, 0, 1, 0 〉)$ is a solution, $𝚌𝚘𝚗𝚜𝚎𝚌𝚞𝚝𝚒𝚟𝚎_𝚐𝚛𝚘𝚞𝚙𝚜_𝚘𝚏_𝚘𝚗𝚎𝚜$ $(〈 1, 2 〉, 〈 0, 1, 0, 0, 0, 1, 1 〉)$ is also a valid solution.
EXAMPLE 2: As a second example, consider the $𝚗𝚟𝚎𝚌𝚝𝚘𝚛$ $(𝙽𝚅𝙴𝙲, 𝚅𝙴𝙲𝚃𝙾𝚁𝚂)$ constraint, which has two arguments $𝙽𝚅𝙴𝙲$ and $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ respectively corresponding to a domain variable and to a collection of collections of domain variables, where all collections have the same number of items. The unique attribute of $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ is denoted by $𝚟𝚎𝚌$ and its type is a collection of domain variables. Each collection is interpreted as a vector and two vectors are distinct if and only if they differ in at least one component. The $𝚗𝚟𝚎𝚌𝚝𝚘𝚛$ constraint forces $𝙽𝚅𝙴𝙲$ to be equal to the number of distinct vectors within $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ . If we permute the components of all vectors with respect to a same permutation we still have the same number of distinct vectors. Within the electronic catalogue this is represented by the following meta-data, $𝚒𝚝𝚎𝚖𝚜_𝚜𝚢𝚗𝚌 ([𝚅𝙴𝙲𝚃𝙾𝚁𝚂 . 𝚟𝚎𝚌], 𝚊𝚕𝚕)$ , to which corresponds the following textual form:

items of $𝚅𝙴𝙲𝚃𝙾𝚁𝚂 . 𝚟𝚎𝚌$ are permutable (same permutation used).

For instance, since $𝚗𝚟𝚎𝚌𝚝𝚘𝚛$ $(2, 〈 𝚟𝚎𝚌 - 〈 1, 1, 8 〉, 𝚟𝚎𝚌 - 〈 5, 1, 6 〉, 𝚟𝚎𝚌 - 〈 1, 1, 8 〉 〉)$ is a solution, any permutation applied simultaneously to the three components of each vector leads to a solution, i.e.:
- $𝚗𝚟𝚎𝚌𝚝𝚘𝚛$ $(2, 〈 𝚟𝚎𝚌 - 〈 1, 1, 8 〉, 𝚟𝚎𝚌 - 〈 5, 1, 6 〉, 𝚟𝚎𝚌 - 〈 1, 1, 8 〉 〉)$ ,
- $𝚗𝚟𝚎𝚌𝚝𝚘𝚛$ $(2, 〈 𝚟𝚎𝚌 - 〈 1, 8, 1 〉, 𝚟𝚎𝚌 - 〈 5, 6, 1 〉, 𝚟𝚎𝚌 - 〈 1, 8, 1 〉 〉)$ ,
- $𝚗𝚟𝚎𝚌𝚝𝚘𝚛$ $(2, 〈 𝚟𝚎𝚌 - 〈 1, 1, 8 〉, 𝚟𝚎𝚌 - 〈 1, 5, 6 〉, 𝚟𝚎𝚌 - 〈 1, 1, 8 〉 〉)$ ,
- $𝚗𝚟𝚎𝚌𝚝𝚘𝚛$ $(2, 〈 𝚟𝚎𝚌 - 〈 1, 8, 1 〉, 𝚟𝚎𝚌 - 〈 1, 6, 5 〉, 𝚟𝚎𝚌 - 〈 1, 8, 1 〉 〉)$ ,
- $𝚗𝚟𝚎𝚌𝚝𝚘𝚛$ $(2, 〈 𝚟𝚎𝚌 - 〈 8, 1, 1 〉, 𝚟𝚎𝚌 - 〈 6, 1, 5 〉, 𝚟𝚎𝚌 - 〈 8, 1, 1 〉 〉)$ ,
- $𝚗𝚟𝚎𝚌𝚝𝚘𝚛$ $(2, 〈 𝚟𝚎𝚌 - 〈 8, 1, 1 〉, 𝚟𝚎𝚌 - 〈 6, 5, 1 〉, 𝚟𝚎𝚌 - 〈 8, 1, 1 〉 〉)$ .
$𝚊𝚝𝚝𝚛𝚜 (𝙲𝙾𝙻𝙻𝙴𝙲𝚃𝙸𝙾𝙽, 𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽)$ denotes the fact that we can permute the attributes of the collection $𝙲𝙾𝙻𝙻𝙴𝙲𝚃𝙸𝙾𝙽$ , not necessarily all items, with respect to a permutation $𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽$ . Attributes that are exchanged must have the same type under the hypothesis that they are ground (e.g., an attribute $𝚊𝚝𝚝𝚛 1$ of type $𝚒𝚗𝚝$ can be exchanged with an attribute $𝚊𝚝𝚝𝚛 2$ of type $𝚍𝚟𝚊𝚛$ .

EXAMPLE: As an example, consider the $𝚜𝚌𝚊𝚕𝚊𝚛_𝚙𝚛𝚘𝚍𝚞𝚌𝚝$ $(𝙻𝙸𝙽𝙴𝙰𝚁𝚃𝙴𝚁𝙼,$ $𝙲𝚃𝚁,$ $𝚅𝙰𝙻)$ constraint, which forces a linear term, represented by a collection with two attributes $𝚌𝚘𝚎𝚏𝚏$ and $𝚟𝚊𝚛$ , to be equal, different, less, greater than or equal, greater, or less than or equal (i.e., depending on the value of $𝙲𝚃𝚁$ ) to $𝚅𝙰𝙻$ . In the ground case we can exchange attributes $𝚌𝚘𝚎𝚏𝚏$ and $𝚟𝚊𝚛$ without affecting the fact that the constraint is satisfied. Within the electronic catalogue this is represented by the following meta-data, $𝚊𝚝𝚝𝚛𝚜 (𝙻𝙸𝙽𝙴𝙰𝚁𝚃𝙴𝚁𝙼, [[𝚌𝚘𝚎𝚏𝚏, 𝚟𝚊𝚛]])$ , to which corresponds the following textual form:

attributes of $𝙻𝙸𝙽𝙴𝙰𝚁𝚃𝙴𝚁𝙼$ are permutable w.r.t. permutation $(𝚌𝚘𝚎𝚏𝚏, 𝚟𝚊𝚛)$ (permutation not necessarily applied to all items).

For instance, since $𝚜𝚌𝚊𝚕𝚊𝚛_𝚙𝚛𝚘𝚍𝚞𝚌𝚝$ $(〈 𝚌𝚘𝚎𝚏𝚏 - 1 𝚟𝚊𝚛 - 1, 𝚌𝚘𝚎𝚏𝚏 - 3 𝚟𝚊𝚛 - 1, 𝚌𝚘𝚎𝚏𝚏 - 1 𝚟𝚊𝚛 - 4, 〉, =, 8)$ is a solution, $𝚜𝚌𝚊𝚕𝚊𝚛_𝚙𝚛𝚘𝚍𝚞𝚌𝚝$ $(〈 𝚌𝚘𝚎𝚏𝚏 - 1 𝚟𝚊𝚛 - 1, 𝚌𝚘𝚎𝚏𝚏 - 1 𝚟𝚊𝚛 - 3, 𝚌𝚘𝚎𝚏𝚏 - 1 𝚟𝚊𝚛 - 4, 〉, =, 8)$ is also a valid solution (i.e., the attributes $𝚌𝚘𝚎𝚏𝚏$ and $𝚟𝚊𝚛$ of the second item were permuted).
$𝚊𝚝𝚝𝚛𝚜_𝚜𝚢𝚗𝚌 (𝙲𝙾𝙻𝙻𝙴𝙲𝚃𝙸𝙾𝙽, 𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽)$ denotes the fact that we can permute the attributes of the collection $𝙲𝙾𝙻𝙻𝙴𝙲𝚃𝙸𝙾𝙽$ , necessarily all items, with respect to a permutation $𝙿𝙴𝚁𝙼𝚄𝚃𝙰𝚃𝙸𝙾𝙽$ . As before, attributes that are exchanged must have the same type under the hypothesis that they are ground.

EXAMPLE: As an example, consider the $𝚌𝚛𝚘𝚜𝚜𝚒𝚗𝚐$ $(𝙽𝙲𝚁𝙾𝚂𝚂, 𝚂𝙴𝙶𝙼𝙴𝙽𝚃𝚂)$ constraint, which forces $𝙽𝙲𝚁𝙾𝚂𝚂$ to be equal to the number of line segments intersections between the line segments defined by the $𝚂𝙴𝙶𝙼𝙴𝙽𝚃𝚂$ collection. Each line segment is defined by the coordinates $(𝚘𝚡, 𝚘𝚢)$ and $(𝚎𝚡, 𝚎𝚢)$ of its two extremities. Note that we can exchange the role of the $x$ and $y$ axes without affecting the number of line segments intersections. Within the electronic catalogue this is represented by the following meta-data, $𝚊𝚝𝚝𝚛𝚜_𝚜𝚢𝚗𝚌 (𝚂𝙴𝙶𝙼𝙴𝙽𝚃𝚂, [[𝚘𝚡, 𝚘𝚢], [𝚎𝚡, 𝚎𝚢]])$ , to which corresponds the following textual form:

attributes of $𝚂𝙴𝙶𝙼𝙴𝙽𝚃𝚂$ are permutable w.r.t. permutation $(𝚘𝚡, 𝚘𝚢)$ $(𝚎𝚡, 𝚎𝚢)$ (permutation applied to all items).

For instance, since $𝚌𝚛𝚘𝚜𝚜𝚒𝚗𝚐$ $(3, 〈 𝚘𝚡 - 1 𝚘𝚢 - 4 𝚎𝚡 - 9 𝚎𝚢 - 2, 𝚘𝚡 - 1 𝚘𝚢 - 1 𝚎𝚡 - 3 𝚎𝚢 - 5, 𝚘𝚡 - 3 𝚘𝚢 - 2 𝚎𝚡 - 7 𝚎𝚢 - 4, 𝚘𝚡 - 9 𝚘𝚢 - 1 𝚎𝚡 - 9 𝚎𝚢 - 4 〉)$ is a solution, $𝚌𝚛𝚘𝚜𝚜𝚒𝚗𝚐$ $(3, 〈 𝚘𝚡 - 4 𝚘𝚢 - 1 𝚎𝚡 - 2 𝚎𝚢 - 9, 𝚘𝚡 - 1 𝚘𝚢 - 1 𝚎𝚡 - 5 𝚎𝚢 - 3, 𝚘𝚡 - 2 𝚘𝚢 - 3 𝚎𝚡 - 4 𝚎𝚢 - 7, 𝚘𝚡 - 1 𝚘𝚢 - 9 𝚎𝚡 - 4 𝚎𝚢 - 9 〉)$ is also a valid solution.
𝚟𝚊𝚕𝚜(𝙰𝚃𝚃𝚁𝙸𝙱𝚄𝚃𝙴𝚂,𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽,𝙿𝙰𝙸𝚁𝚂,𝚂𝙾𝚄𝚁𝙲𝙴,𝚃𝙰𝚁𝙶𝙴𝚃) denotes the fact that we can permute some source value with some distinct target value. The kind of value permutation we can perform is parameterised by five parameters:
- $𝙰𝚃𝚃𝚁𝙸𝙱𝚄𝚃𝙴𝚂$ is a list of paths of the form $𝙰𝚁𝙶 0$ or $𝙰𝚁𝙶 1 . \dots . 𝙰𝚁𝙶𝚗 . 𝚊𝚝𝚝𝚛$ $(n \geq 1)$ , where:
  - $𝙰𝚁𝙶 0$ is an argument of the global constraint of type domain variable, integer, or collection of domain variables or integers.
  - $𝙰𝚁𝙶 1 . \dots . 𝙰𝚁𝙶𝚗 . 𝚊𝚝𝚝𝚛$ is a path to an integer attribute or to a collection of integers attribute of the global constraint. $𝙰𝚁𝙶 1$ , $𝙰𝚁𝙶 2$ , ..., $𝙰𝚁𝙶𝚗$ are collections and $𝚊𝚝𝚝𝚛$ is an attribute of $𝙰𝚁𝙶𝚗$ of type domain variable, integer, or collection of domain variables or integers. In this last context, all collections have the same number of items since we can only exchange tuples of values that have the same number of components. The path does not necessarily start from a top level collection.
  Its purpose is to define the scope where the exchange of values, or tuples of values, will take place. Note that:
  - The case corresponding to $𝙰𝚁𝙶 0$ allows to express the fact that the value of an integer argument can be changed in such a way that we still have a solution.
  - The case when $𝙰𝚁𝙶 1$ is not a top level collection allows to express the fact that the exchange of value takes place within a nested collection. In this context this implicitly defines several scopes for the exchange of values.
  - The case where $𝙰𝚁𝙶 1 . \dots . 𝙰𝚁𝙶𝚗 . 𝚊𝚝𝚝𝚛$ is a path to a collection of variables or integers allows expressing swap between tuples of values (i.e., the exchange of values is generalised to the exchange of tuples of values).
- $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽$ usually defines a partition $𝒫$ of integer values. Only when $𝙰𝚁𝙶 1 . \dots . 𝙰𝚁𝙶𝚗 . 𝚊𝚝𝚝𝚛$ is a path to a collection of variables or integers, $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽$ defines a partition of tuples of integer values. For the time being we focus on the first case, i.e., a partition of integer values. Its aim is to define classes of values from which the source and target values will be selected. In order to define a partition $𝒫$ we first introduce the notion of set of values generator. Within these definitions, $u$ and $v$ both denote (1) an integer value, or (2) an argument of the constraint of type integer or domain variable, or (3) a term of the form $| 𝙰𝚁𝙶 |$ where $𝙰𝚁𝙶$ is an argument of type collection denoting the number of items of the collection, (4) a sum or difference of elements of the form (1), (2) or (3). We have two kinds of generators, namely:
  - A basic set of values generator is defined by one of those:
    - $𝙰𝚁𝙶 . 𝚊𝚝𝚝𝚛$ , where $𝙰𝚁𝙶$ is an argument of type collection and $𝚊𝚝𝚝𝚛$ is an attribute of $𝙰𝚁𝙶$ of type integer or domain variable, denotes the set of all values assigned to $𝙰𝚁𝙶 . 𝚊𝚝𝚝𝚛$ .
    - $𝚗𝚘𝚝𝚒𝚗 (𝙰𝚁𝙶 . 𝚊𝚝𝚝𝚛)$ , where $𝙰𝚁𝙶$ is an argument of type collection and $𝚊𝚝𝚝𝚛$ is an attribute of $𝙰𝚁𝙶$ of type integer or domain variable, denotes the set of all elements of $ℤ$ that are not assigned to $𝙰𝚁𝙶 . 𝚊𝚝𝚝𝚛$ .
    - $𝚍𝚒𝚏𝚏 (𝙰𝚁𝙶 1 . 𝚊𝚝𝚝𝚛 1, 𝙰𝚁𝙶 2 . 𝚊𝚝𝚝𝚛 2)$ , where $𝙰𝚁𝙶 1$ (respectively $𝙰𝚁𝙶 2$ ) is an argument of type collection and $𝚊𝚝𝚝𝚛 1$ (respectively $𝚊𝚝𝚝𝚛 2$ ) is an attribute of $𝙰𝚁𝙶 1$ (respectively $𝙰𝚁𝙶 2$ ) of type integer or domain variable, denotes the set of all elements of $ℤ$ that are assigned to $𝙰𝚁𝙶 1 . 𝚊𝚝𝚝𝚛 1$ but not to $𝙰𝚁𝙶 2 . 𝚊𝚝𝚝𝚛 2$ .
    - $u$ , denotes the set ${u}$ .
    - $𝑐𝑚𝑝 (𝚞)$ , $(𝑐𝑚𝑝 \in {=, \neq, <, \geq, >, \leq})$ , denotes the set of all integers $e$ such that the comparison $e 𝑐𝑚𝑝 u$ holds.
    - $𝚒𝚗 (u, v)$ , $(u \leq v)$ , denotes the set of all integers located in interval $[u, v]$ .
    - $𝚗𝚘𝚝𝚒𝚗 (u, v)$ , $(u \leq v)$ , denotes the set of all integers not located in interval $[u, v]$ .
    - $𝚖𝚘𝚍 (u, v)$ , $(0 < v < u, u, v \in ℕ^{+})$ , denotes all integer values in $ℤ$ that have $v$ as remainder when divided by $u$ .remainder $(a, n) = a - n ⌊\frac{a}{n}⌋$ .
  - Given set of values generators $𝒮_{1}$ , $𝒮_{2}$ , $\dots$ , $𝒮_{n}$ $(n \geq 2)$ , a compound set of values generator is defined by:
    - $[𝒮_{1}, 𝒮_{2}, \dots, 𝒮_{n}]$ denotes all values that are in at least one of the sets $𝒮_{1}$ , $𝒮_{2}$ , $\dots$ , $𝒮_{n}$ .
    - $𝚗𝚘𝚝𝚒𝚗 ([𝒮_{1}, 𝒮_{2}, \dots, 𝒮_{n}])$ denotes all values of $ℤ$ that are not in any set $𝒮_{1}$ , $𝒮_{2}$ , $\dots$ , $𝒮_{n}$ .
  We now describe the different partition generators. Within the description, $𝒮$ and $𝒟$ denote set of values generators. Classes of a partition are ordered. Unless explicitly specified, classes are ordered with respect to the smallest element they contain.
  - $𝚒𝚗𝚝$ denotes a partition $𝒫$ where, to each element of $ℤ$ corresponds a specific class of $𝒫$ containing just that element.
  - $𝚒𝚗𝚝 (𝒮)$ denotes a partition $𝒫$ where, to each element of $𝒮$ corresponds a specific class of $𝒫$ containing just that element.
  - $𝚊𝚕𝚕$ denotes a partition $𝒫$ containing a single class of values corresponding to all integer values in $ℤ$ .
  - $𝚊𝚕𝚕 (𝒮)$ denotes a partition $𝒫$ containing a single class of values corresponding to the elements of $𝒮$ .
  - $𝚌𝚘𝚖𝚙 (𝒮)$ denotes of partition $𝒫$ containing two classes of values: a first class corresponding to the elements of $𝒮$ , and a second class consisting of all elements of $ℤ$ that are not in $𝒮$ .
  - $𝚌𝚘𝚖𝚙_𝚍𝚒𝚏𝚏 (𝒮, 𝒟)$ denotes of partition $𝒫$ containing two classes of values: a first class corresponding to the elements of $𝒮$ but not in $𝒟$ , and a second class consisting of all elements of $ℤ$ that are neither in $𝒮$ nor in $𝒟$ .
  - $𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕𝚜 (u)$ , $(u > 0)$ , denotes a partition $𝒫$ containing intervals of the form $[k \cdot u, k \cdot u + u - 1]$ , $k \in ℤ$ .
  - $𝚖𝚘𝚍 (u)$ , $(u > 0)$ , denotes a partition $𝒫$ such that each class of $𝒫$ is made up from all integers in $ℤ$ that have the same remainder when divided by $u$ .remainder $(a, n) = a - n ⌊ \frac{a}{n} ⌋$ .
  - $𝚙𝚊𝚛𝚝 (P)$ , where $P$ is a collection of collections of integers passed as one of the arguments of the constraint, where each integer occurs once, denotes a partition $𝒫$ such that each class corresponds to the elements of one of the collections of $P$ . Classes are ordered with respect to their occurrences in $P$ .
  When $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽$ defines a partition of tuples, where each tuple consists of $k$ integers, $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽$ can only be set to $𝚒𝚗𝚝$ . In this context $𝚒𝚗𝚝$ denotes a partition $𝒫$ where, to each element of $ℤ^{k}$ corresponds a specific class of $𝒫$ containing just that element.
- $𝙿𝙰𝙸𝚁𝚂$ is one of the symbols $\neq$ , $=$ , $<$ , $\geq$ , $>$ , $\leq$ , or $𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎$ . It specifies a set of pairs ${(p_{i_{1}}, p_{j_{1}}), (p_{i_{2}}, p_{j_{2}}), \dots, (p_{i_{n}}, p_{j_{n}})}$ of elements of the partition $𝒫$ such that, when $𝙿𝙰𝙸𝚁𝚂$ is different from $𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎$ ,When $𝙿𝙰𝙸𝚁𝚂$ is equal to $𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎$ we just consider all possible pairs. the condition $i_{k} 𝙿𝙰𝙸𝚁𝚂 j_{k}$ holds for all $k \in [1, n]$ . The aim of the $𝙿𝙰𝙸𝚁𝚂$ parameter is to allow to specify which partitions of $𝒫$ the source value $u$ and the target value $v$ should belong to. In fact there should exist a pair $(p_{i_{k}}, p_{j_{k}})$ , $(k \in [1, n])$ , such that $u \in p_{i_{k}}$ and $v \in p_{j_{k}}$ .
- $𝚂𝙾𝚄𝚁𝙲𝙴$ is one of the options $𝚊𝚕𝚕$ or $𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎$ :
  - When set to $𝚊𝚕𝚕$ it indicates that all occurrences of the source value should be replaced by the target value. All occurrences of the target value, if it is used, should also be replaced by the source value.
  - When set to $𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎$ it tells that not necessarily all occurrences of the source value should be replaced. The target value is left unchanged.
- $𝚃𝙰𝚁𝙶𝙴𝚃$ is one of the options $𝚒𝚗$ or $𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎$ :
  - When set to $𝚒𝚗$ it indicates that the target value should correspond to an already existing value of $𝙰𝚁𝙶 . 𝚊𝚝𝚝𝚛$ .
  - When set to $𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎$ it tells that the target value can either correspond to an already existing value of $𝙰𝚁𝙶 . 𝚊𝚝𝚝𝚛$ , or designate a new value.
  We now define the set of conditions we must have in order to exchange a source and a target values. Consider,
  1. a ground instance of a global constraint $C$ ,
  2. a path $𝙿𝙰𝚃𝙷$ that designates either an argument of type integer, or an integer attribute of a collection that occurs, possibly in a nested way, as one of the arguments of $C$ ,
  3. the sets of values $𝒱_{1}, 𝒱_{2}, \dots, 𝒱_{h}$ that are assigned to $𝙿𝙰𝚃𝙷$ in the ground instance of $C$ ,We may have more than one set when the path does not start from a top level collection.
  4. a partition of integer values $𝒫$ derived from $𝙿𝙰𝚁𝚃𝙸𝚃𝙸𝙾𝙽$ ,
  5. a set of pairs ${(p_{i_{1}}, p_{j_{1}}), (p_{i_{2}}, p_{j_{2}}), \dots, (p_{i_{n}}, p_{j_{n}})}$ of elements of the partition $𝒫$ such that the condition $𝙿𝙰𝙸𝚁𝚂 = 𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎 \lor i_{k} 𝙿𝙰𝙸𝚁𝚂 j_{k}$ holds for all $k \in [1, n]$ ,
  6. a $𝚃𝙰𝚁𝙶𝙴𝚃$ option.
  Given one of the sets of values $𝒱_{α}$ , $(1 \leq α \leq h)$ , a source value $u$ can be permuted with a target value $v$ if and only if the following conditions are all satisfied:
  1. $u \neq v$ (source and target values should be distinct),
  2. $u \in 𝒱_{α}$ (source value, i.e., value that is replaced, should be part of the solution),
  3. $\exists k | u \in p_{i_{k}} \land v \in p_{j_{k}}$ (source and target values should be located in the appropriate partition classes),
  4. $𝚃𝙰𝚁𝙶𝙴𝚃 = 𝚒𝚗 \Rightarrow v \in 𝒱_{α}$ (if $𝚃𝙰𝚁𝙶𝙴𝚃 = 𝚒𝚗$ then the target value should also be part of the solution).
  If $𝚂𝙾𝚄𝚁𝙲𝙴$ is equal to $𝚊𝚕𝚕$ we replace each occurrence of $u$ by $v$ , and conversely each occurrence of $v$ by $u$ . Otherwise we replace at least one occurrence of $u$ by $v$ .
  
  Without loss of generality, when $𝙿𝙰𝚃𝙷$ designates a collection of integer values or domain variables, the exchange of tuples of values is defined in a similar way.
We now provide a number of examples of value symmetry and illustrate how to encode them with the five parameters we just introduced. We start from the most common value symmetry, namely exchanging all occurrences of two distinct values or replacing all occurrences of a value by an unused value.
EXAMPLE 1: As a first example, consider the $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ $(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$ constraint, which forces all variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ to take distinct values. Note that we can exchange two assigned values of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ , or replace an assigned value of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ by a new value, i.e., a value that is not yet assigned to any variable of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ . Within the electronic catalogue this is represented by the following meta-data, $𝚟𝚊𝚕𝚜 ([𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛], 𝚒𝚗𝚝, \neq, 𝚊𝚕𝚕, 𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎)$ , to which corresponds the following textual form:

Two distinct values of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ can be swapped; a value of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ can be renamed to any unused value.

For instance, since $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ $(〈 5, 1, 9, 3 〉)$ is a solution, we can replace value 9 by a not yet assigned value, 0 for instance, and get another valid solution $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ $(〈 5, 1, 0, 3 〉)$ .

The five parameters of $𝚟𝚊𝚕𝚜 ([𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛], 𝚒𝚗𝚝, \neq, 𝚊𝚕𝚕, 𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎)$ have the following meaning:
- $[𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛]$ indicates that the modification takes place within the values assigned to the $𝚟𝚊𝚛$ attribute of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection.
- $𝚒𝚗𝚝$ defines the partition of values $𝒫 = \dots, {- 1}, {0}, {1}, \dots$ .
- $\neq$ indicates that the exchange of values takes place between two distinct elements of $𝒫$ .
- $𝚊𝚕𝚕$ specifies that all occurrences of the source value have to be exchanged with all occurrences of the target value.
- $𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎$ tells that the source value can be replaced by an already existing value or by a new value, i.e., a value not already used in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ .
EXAMPLE 2: As a second example, consider the $𝚗𝚟𝚊𝚕𝚞𝚎$ $(𝙽𝚅𝙰𝙻, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$ constraint, which forces $𝙽𝚅𝙰𝙻$ to be equal to the number of distinct values assigned to the variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ . Note that we can exchange all occurrences of two distinct values of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ , or replace all occurrences of an assigned value of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ by a new value, i.e., a value that is not yet assigned to any variable of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ . Within the electronic catalogue this is represented by the following meta-data, $𝚟𝚊𝚕𝚜 ([𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛], 𝚒𝚗𝚝, \neq, 𝚊𝚕𝚕, 𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎)$ , to which corresponds the following textual form:

All occurrences of two distinct values of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ can be swapped; all occurrences of a value of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ can be renamed to any unused value.

For instance, since $𝚗𝚟𝚊𝚕𝚞𝚎$ $(4, 〈 3, 1, 7, 1, 6 〉)$ is a solution, we can replace all occurrences of value 1 by a not yet assigned value, 8 for instance, and get another valid solution $𝚗𝚟𝚊𝚕𝚞𝚎$ $(4, 〈 3, 8, 7, 8, 6 〉)$ . We can also swap all occurrences of value 1 and value 3, and get another valid solution $𝚗𝚟𝚊𝚕𝚞𝚎$ $(4, 〈 1, 3, 7, 3, 6 〉)$ .

The five parameters of $𝚟𝚊𝚕𝚜 ([𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛], 𝚒𝚗𝚝, \neq, 𝚊𝚕𝚕, 𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎)$ have the following meaning:
- $[𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛]$ indicates that the modification takes place within the values assigned to the $𝚟𝚊𝚛$ attribute of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection.
- $𝚒𝚗𝚝$ defines the partition of values $𝒫 = \dots, {- 1}, {0}, {1}, \dots$ .
- $\neq$ indicates that the exchange of values takes place between two distinct elements of $𝒫$ .
- $𝚊𝚕𝚕$ specifies that all occurrences of the source value have to be exchanged with all occurrences of the target value.
- $𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎$ tells that the source value can be replaced by an already existing value or by a new value, i.e., a value not already used in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ .
We now introduce a third and a fourth example where the meta-data used for describing value symmetry, $𝚟𝚊𝚕𝚜 ([𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛], 𝚒𝚗𝚝, \neq, 𝚊𝚕𝚕, 𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎)$ , is replaced by $𝚟𝚊𝚕𝚜 ([𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛], 𝚒𝚗𝚝, \neq, 𝚊𝚕𝚕, 𝚒𝚗)$ , i.e., we are not allowed to introduce an unused value.
EXAMPLE 3: As a third example, consider the $𝚊𝚕𝚕_𝚖𝚒𝚗_𝚍𝚒𝚜𝚝$ $(𝙼𝙸𝙽𝙳𝙸𝚂𝚃,$ $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$ constraint, which forces for each pair $({𝚟𝚊𝚛}_{i}, {𝚟𝚊𝚛}_{j})$ of distinct variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ that $| {𝚟𝚊𝚛}_{i} - {𝚟𝚊𝚛}_{j} | \geq 𝙼𝙸𝙽𝙳𝙸𝚂𝚃$ . Note that we can exchange two occurrences of distinct values of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ , but we cannot replace an existing value $u$ by a new value $v$ (since the new value $v$ may be too close from another existing value $w$ , i.e., $| v - w | < 𝙼𝙸𝙽𝙳𝙸𝚂𝚃$ ). Within the electronic catalogue this is represented by the following meta-data, $𝚟𝚊𝚕𝚜 ([𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛], 𝚒𝚗𝚝, \neq, 𝚊𝚕𝚕, 𝚒𝚗)$ , to which corresponds the following textual form:

Two distinct values of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ can be swapped.

For instance, since $𝚊𝚕𝚕_𝚖𝚒𝚗_𝚍𝚒𝚜𝚝$ $(2, 〈 5, 1, 9, 3 〉)$ is a solution, we can swap values 5 and 9, and get another valid solution $𝚊𝚕𝚕_𝚖𝚒𝚗_𝚍𝚒𝚜𝚝$ $(2, 〈 9, 1, 5, 3 〉)$ .

The five parameters of $𝚟𝚊𝚕𝚜 ([𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛], 𝚒𝚗𝚝, \neq, 𝚊𝚕𝚕, 𝚒𝚗)$ have the following meaning:
- $[𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛]$ indicates that the modification takes place within the values assigned to the $𝚟𝚊𝚛$ attribute of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection.
- $𝚒𝚗𝚝$ defines the partition of values $𝒫 = \dots, {- 1}, {0}, {1}, \dots$ .
- $\neq$ indicates that the exchange of values takes place between two distinct elements of $𝒫$ .
- $𝚊𝚕𝚕$ specifies that all occurrences of the source value have to be exchanged with all occurrences of the target value.
- $𝚒𝚗$ tells that the source value has to be replaced by an already existing value in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ .
EXAMPLE 4: As a fourth example, consider the $𝚖𝚒𝚗𝚒𝚖𝚞𝚖$ $(𝙼𝙸𝙽,$ $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$ constraint, which forces $𝙼𝙸𝙽$ to be equal to the minimum value of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ . Note that we can exchange all occurrences of two distinct values of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ , but we cannot replace an existing value $u$ by a new value $v$ (since the new value $v$ may be smaller than $𝙼𝙸𝙽$ ). Within the electronic catalogue this is represented by the following meta-data, $𝚟𝚊𝚕𝚜 ([𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛], 𝚒𝚗𝚝, \neq, 𝚊𝚕𝚕, 𝚒𝚗)$ , to which corresponds the following textual form:

All occurrences of two distinct values of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ can be swapped.

For instance, since $𝚖𝚒𝚗𝚒𝚖𝚞𝚖$ $(2, 〈 3, 2, 7, 2, 6 〉)$ is a solution, we can swap values 2 and 6, and get another valid solution $𝚖𝚒𝚗𝚒𝚖𝚞𝚖$ $(2, 〈 3, 6, 7, 6, 2 〉)$ .

The five parameters of $𝚟𝚊𝚕𝚜 ([𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛], 𝚒𝚗𝚝, \neq, 𝚊𝚕𝚕, 𝚒𝚗)$ have the following meaning:
- $[𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛]$ indicates that the modification takes place within the values assigned to the $𝚟𝚊𝚛$ attribute of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection.
- $𝚒𝚗𝚝$ defines the partition of values $𝒫 = \dots, {- 1}, {0}, {1}, \dots$ .
- $\neq$ indicates that the exchange of values takes place between two distinct elements of $𝒫$ .
- $𝚊𝚕𝚕$ specifies that all occurrences of the source value have to be exchanged with all occurrences of the target value.
- $𝚒𝚗$ tells that the source value has to be replaced by an already existing value in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ .
We now present three examples where, using the partition generator $𝚌𝚘𝚖𝚙 (𝒮)$ , we consider two classes of values: a first class consisting of elements of $𝒮$ and a second class of elements of $ℤ$ not in $𝒮$ . The first example corresponds to a value symmetry where values from the same class are exchanged, while the two other examples consider permutation of values between distinct classes with respect to a given class ordering.
EXAMPLE 5: As a fifth example, consider the $𝚊𝚖𝚘𝚗𝚐$ $(𝙽𝚅𝙰𝚁, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚅𝙰𝙻𝚄𝙴𝚂)$ constraint, which forces $𝙽𝚅𝙰𝚁$ to be equal to the number of variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ that are assigned a value in $𝚅𝙰𝙻𝚄𝙴𝚂$ . We focus on exchanges of values that take place within $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ . Note that, given a value that both occurs in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ and in $𝚅𝙰𝙻𝚄𝙴𝚂$ , we can replace it by any value in $𝚅𝙰𝙻𝚄𝙴𝚂$ . But we can also replace a value that occurs in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ , but not in $𝚅𝙰𝙻𝚄𝙴𝚂$ , by any value not in $𝚅𝙰𝙻𝚄𝙴𝚂$ . Within the electronic catalogue this is represented by the following meta-data, $𝚟𝚊𝚕𝚜 ([𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛], 𝚌𝚘𝚖𝚙 (𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚟𝚊𝚕), =, 𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎, 𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎)$ , to which corresponds the following textual form:

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

For instance, since $𝚊𝚖𝚘𝚗𝚐$ $(3, 〈 4, 5, 5, 4, 1 〉, 〈 1, 5, 8 〉)$ is a solution, we can swap the first occurrence of value 5 with the second occurrence of value 4 in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ , and get another valid solution $𝚊𝚖𝚘𝚗𝚐$ $(3, 〈 4, 4, 5, 5, 1 〉, 〈 1, 5, 8 〉)$ .

The five parameters of $𝚟𝚊𝚕𝚜 ([𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛], 𝚌𝚘𝚖𝚙 (𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚟𝚊𝚕), =, 𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎,$ $𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎)$ have the following meaning:
- $[𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛]$ indicates that the modification takes place within the values assigned to the $𝚟𝚊𝚛$ attribute of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection.
- $𝚌𝚘𝚖𝚙 (𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚟𝚊𝚕)$ defines two set of values, a first set $𝒮_{1}$ corresponding to all values in $𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚟𝚊𝚕$ , and a second set $𝒮_{2}$ corresponding to all values not in $𝚅𝙰𝙻𝚄𝙴𝚂 . 𝚟𝚊𝚕$ .
- $=$ indicates that the exchange of values takes place within the same set, i.e., within $𝒮_{1}$ or within $𝒮_{2}$ .
- $𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎$ specifies that one occurrence of the source value has to be replaced by the target value.
- $𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎$ tells that the source value can be replaced by an already existing value or by a new value, i.e., a value not already used in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ .
EXAMPLE 6: As a sixth example, consider the $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ $(𝙽, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚅𝙰𝙻𝚄𝙴)$ constraint, which forces at least $𝙽$ variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ to be assigned value $𝚅𝙰𝙻𝚄𝙴$ . Note that, given an occurrence of value that belongs to $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ that is different from $𝚅𝙰𝙻𝚄𝙴$ , we can replace it by any other value that is also different from $𝚅𝙰𝙻𝚄𝙴$ .Within the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ , this swap does not change the number of variables that are assigned value $𝚅𝙰𝙻𝚄𝙴$ . But we can also replace it by value $𝚅𝙰𝙻𝚄𝙴$ since this does not decrease the number of variables that are assigned value $𝚅𝙰𝙻𝚄𝙴$ . Within the electronic catalogue this is represented by the following meta-data, $𝚟𝚊𝚕𝚜 ([𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛], 𝚌𝚘𝚖𝚙 (𝚅𝙰𝙻𝚄𝙴), \geq, 𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎, 𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎)$ , to which corresponds the following textual form:

An occurrence of a value of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ that is different from $𝚅𝙰𝙻𝚄𝙴$ can be replaced by any other value.

For instance, since $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ $(2, 〈 4, 2, 4, 5, 2 〉, 4)$ is a solution, we can replace the second occurrence of value 2 with a value that is different from value 4, e.g., value 8, and get another valid solution $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ $(2, 〈 4, 2, 4, 5, 8 〉, 4)$ . We can also replace the second occurrence of value 2 with value 4 and get another valid solution $𝚊𝚝𝚕𝚎𝚊𝚜𝚝$ $(2, 〈 4, 2, 4, 5, 4 〉, 4)$ .

The five parameters of $𝚟𝚊𝚕𝚜 ([𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛], 𝚌𝚘𝚖𝚙 (𝚅𝙰𝙻𝚄𝙴), \geq, 𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎,$ $𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎)$ have the following meaning:
- $[𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛]$ indicates that the modification takes place within the values assigned to the $𝚟𝚊𝚛$ attribute of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection.
- $𝚌𝚘𝚖𝚙 (𝚅𝙰𝙻𝚄𝙴)$ defines two set of values, a first set $𝒮_{1}$ containing only value $𝚅𝙰𝙻𝚄𝙴$ , and a second set $𝒮_{2}$ corresponding to all values different from $𝚅𝙰𝙻𝚄𝙴$ .
- $\geq$ indicates that the the source and target values should respectively belong to sets $𝒮_{i}$ and $𝒮_{j}$ where $i \geq j$ :
  1. If the source value is different from $𝚅𝙰𝙻𝚄𝙴$ (i.e., the source value belongs to $𝒮_{2}$ ), then the target value can indifferently be equal or not equal to $𝚅𝙰𝙻𝚄𝙴$ (i.e., the target value belongs to $𝒮_{1}$ or $𝒮_{2}$ ).
  2. If the source value is equal to $𝚅𝙰𝙻𝚄𝙴$ (i.e., the source value belongs to $𝒮_{1}$ ), then the target value is equal to $𝚅𝙰𝙻𝚄𝙴$ (i.e., the target value also belongs to $𝒮_{1}$ ). But in this case no exchange can take place since the source and target values are identical.
- $𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎$ specifies that one occurrence of the source value has to be replaced by the target value.
- $𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎$ tells that the source value can be replaced by an already existing value or by a new value, i.e., a value not already used in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ .
EXAMPLE 7: As a seventh example, consider the $𝚊𝚝𝚖𝚘𝚜𝚝$ $(𝙽, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚅𝙰𝙻𝚄𝙴)$ constraint, which forces at most $𝙽$ variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ to be assigned value $𝚅𝙰𝙻𝚄𝙴$ . Note that, given an occurrence of value that belongs to $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ , and that is different from $𝚅𝙰𝙻𝚄𝙴$ , we can replace it by any other value that is also different from $𝚅𝙰𝙻𝚄𝙴$ .Within the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ , this swap does not change the number of variables that are assigned value $𝚅𝙰𝙻𝚄𝙴$ . But we can also replace an occurrence of value $𝚅𝙰𝙻𝚄𝙴$ by a value that is different from $𝚅𝙰𝙻𝚄𝙴$ , since this does not increase the number of variables that are assigned value $𝚅𝙰𝙻𝚄𝙴$ . Within the electronic catalogue this is represented by the following meta-data, $𝚟𝚊𝚕𝚜 ([𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛], 𝚌𝚘𝚖𝚙 (𝚅𝙰𝙻𝚄𝙴), \leq, 𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎, 𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎)$ , to which corresponds the following textual form:

An occurrence of a value of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ can be replaced by any other value that is different from $𝚅𝙰𝙻𝚄𝙴$ .

For instance, since $𝚊𝚝𝚖𝚘𝚜𝚝$ $(1, 〈 4, 2, 4, 5 〉, 2)$ is a solution, we can replace the second occurrence of value 4 with a value that is different from value 2, e.g., value 8, and get another valid solution $𝚊𝚝𝚖𝚘𝚜𝚝$ $(1, 〈 4, 2, 8, 5 〉, 2)$ . But, within $𝚊𝚝𝚖𝚘𝚜𝚝$ $(1, 〈 4, 2, 4, 5 〉, 2)$ , we can also replace value 2 with any other value, e.g. value 4 and get another valid solution $𝚊𝚝𝚖𝚘𝚜𝚝$ $(1, 〈 4, 4, 4, 5 〉, 2)$ .

The five parameters of $𝚟𝚊𝚕𝚜 ([𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛], 𝚌𝚘𝚖𝚙 (𝚅𝙰𝙻𝚄𝙴), \leq, 𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎,$ $𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎)$ have the following meaning:
- $[𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛]$ indicates that the modification takes place within the values assigned to the $𝚟𝚊𝚛$ attribute of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection.
- $𝚌𝚘𝚖𝚙 (𝚅𝙰𝙻𝚄𝙴)$ defines two set of values, a first set $𝒮_{1}$ containing only value $𝚅𝙰𝙻𝚄𝙴$ , and a second set $𝒮_{2}$ corresponding to all values different from $𝚅𝙰𝙻𝚄𝙴$ .
- $\leq$ indicates that the the source and target values should respectively belong to sets $𝒮_{i}$ and $𝒮_{j}$ where $i \leq j$ :
  1. If the source value is different from $𝚅𝙰𝙻𝚄𝙴$ (i.e., the source value belongs to $𝒮_{2}$ ), then the target value is also different from $𝚅𝙰𝙻𝚄𝙴$ (i.e., the target value belongs to $𝒮_{2}$ ). This supports the fact that we do not want to increase the number of occurrences of value $𝚅𝙰𝙻𝚄𝙴$ .
  2. If the source value is equal to $𝚅𝙰𝙻𝚄𝙴$ (i.e., the source value belongs to $𝒮_{1}$ ), then there is no restriction on the target value (i.e., the target value belongs to $𝒮_{1}$ or to $𝒮_{2}$ ). But the set $𝒮_{1}$ is not relevant since the target value would also be fixed to $𝚅𝙰𝙻𝚄𝙴$ , and, in this context, no exchange can take place.
- $𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎$ specifies that one occurrence of the source value has to be replaced by the target value.
- $𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎$ tells that the source value can be replaced by an already existing value or by a new value, i.e., a value not already used in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ .
We now illustrate the fact that the scope of value symmetry can sometimes be extended to several collections of variables. For this purpose we consider the $𝚌𝚘𝚖𝚖𝚘𝚗$ constraint.
EXAMPLE 8: Consider the $𝚌𝚘𝚖𝚖𝚘𝚗$ $(𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1, 𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1,$ $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2)$ constraint, which forces the two following conditions:
- $𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1$ is the number of variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ taking a value in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ .
- $𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2$ is the number of variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ taking a value in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ .
Note that we can exchange all occurrences of two distinct values of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ or $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ , or replace all occurrences of an assigned value of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ or $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ by a new value, i.e., a value that is not yet assigned to any variable of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ and $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ . Within the electronic catalogue this is represented by the following meta-data, $𝚟𝚊𝚕𝚜 ([𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 . 𝚟𝚊𝚛, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 . 𝚟𝚊𝚛], 𝚒𝚗𝚝, \neq, 𝚊𝚕𝚕, 𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎)$ , to which corresponds the following textual form:

All occurrences of two distinct values in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 . 𝚟𝚊𝚛$ or $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 . 𝚟𝚊𝚛$ can be swapped; all occurrences of a value in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 . 𝚟𝚊𝚛$ or $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 . 𝚟𝚊𝚛$ can be renamed to any unused value.

For instance, since $𝚌𝚘𝚖𝚖𝚘𝚗$ $(3, 4, 〈 1, 9, 1, 5 〉, 〈 2, 1, 9, 9, 6, 9 〉)$ is a solution, we can replace all occurrences of value 1 by a not yet assigned value, 7 for instance, and get another valid solution $𝚌𝚘𝚖𝚖𝚘𝚗$ $(3, 4, 〈 7, 9, 7, 5 〉, 〈 2, 7, 9, 9, 6, 9 〉)$ .

The five parameters of $𝚟𝚊𝚕𝚜 ([𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 . 𝚟𝚊𝚛, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 . 𝚟𝚊𝚛], 𝚒𝚗𝚝, \neq, 𝚊𝚕𝚕,$ $𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎)$ have the following meaning:
- $[𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 . 𝚟𝚊𝚛, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 . 𝚟𝚊𝚛]$ indicates that the modification takes place within the values assigned to the $𝚟𝚊𝚛$ attribute of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ and $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ collections.
- $𝚒𝚗𝚝$ defines the partition of values $𝒫 = \dots, {- 1}, {0}, {1}, \dots$ .
- $\neq$ indicates that the exchange of values takes place between two distinct elements of $𝒫$ .
- $𝚊𝚕𝚕$ specifies that all occurrences of the source value have to be exchanged with all occurrences of the target value.
- $𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎$ tells that the source value can be replaced by an already existing value or by a new value, i.e., a value not already used in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ or $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ .
We now present an example that illustrates the fact that value symmetry can also occur between two arguments that both correspond to a domain variable, i.e., not just between the variables of a collection of variables. For this purpose we consider the $𝚕𝚎𝚚$ constraint.
EXAMPLE 9: Consider the $𝚕𝚎𝚚$ $(𝚅𝙰𝚁 1, 𝚅𝙰𝚁 2)$ constraint, which forces $𝚅𝙰𝚁 1$ to be less than or equal to $𝚅𝙰𝚁 2$ . Note that $𝚅𝙰𝚁 1$ can be decreased to any value, and that $𝚅𝙰𝚁 1$ can be increased up to $𝚅𝙰𝚁 2$ . Similarly, $𝚅𝙰𝚁 2$ can be increased to any value, and $𝚅𝙰𝚁 2$ can be decreased down to $𝚅𝙰𝚁 1$ . Within the electronic catalogue this is respectively represented by the following meta-data, $𝚟𝚊𝚕𝚜 ([𝚅𝙰𝚁 1], 𝚒𝚗𝚝 (\leq (𝚅𝙰𝚁 2)), \neq, 𝚊𝚕𝚕, 𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎)$ and $𝚟𝚊𝚕𝚜 ([𝚅𝙰𝚁 2], 𝚒𝚗𝚝 (\geq (𝚅𝙰𝚁 1)), \neq, 𝚊𝚕𝚕, 𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎)$ , to which corresponds the following textual form:

$𝚅𝙰𝚁 1$ can be replaced by any value $\leq$ $𝚅𝙰𝚁 2$ ;

$𝚅𝙰𝚁 2$ can be replaced by any value $\geq$ $𝚅𝙰𝚁 1$ .

For instance, since $𝚕𝚎𝚚$ $(2, 9)$ is a solution, we can replace value 2 by any value less than or equal to 9, e.g. value 5 and get another valid solution $𝚕𝚎𝚚$ $(5, 9)$ . But, within $𝚕𝚎𝚚$ $(2, 9)$ , we can also replace value 9 with any other value greater than or equal to 2, e.g. value 4 and get another valid solution $𝚕𝚎𝚚$ $(2, 4)$ .

The five parameters of $𝚟𝚊𝚕𝚜 ([𝚅𝙰𝚁 1], 𝚒𝚗𝚝 (\leq (𝚅𝙰𝚁 2)), \neq, 𝚊𝚕𝚕, 𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎)$ have the following meaning:
- $[𝚅𝙰𝚁 1]$ indicates that the modification takes place within the value assigned to the argument $𝚅𝙰𝚁 1$ of the constraint $𝚕𝚎𝚚$ .
- $𝚒𝚗𝚝 (\leq (𝚅𝙰𝚁 2))$ defines the partition of values $𝒫 = \dots, {𝚅𝙰𝚁 2 - 2}, {𝚅𝙰𝚁 2 - 1}, {𝚅𝙰𝚁 2}$ (i.e., we only consider values that are less than or equal to $𝚅𝙰𝚁 2$ ).
- $\neq$ indicates that the exchange of values takes place between two distinct elements of $𝒫$ .
- $𝚊𝚕𝚕$ specifies that all occurrences of the source value have to be replaced by the target value. Note that, since the scope of the change is reduced to a single variable, we have one occurrence of the source value and no occurrence of the target value.
- $𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎$ tells that the source value will be replaced by a new value.
The meta-data $𝚟𝚊𝚕𝚜 ([𝚅𝙰𝚁 2], 𝚒𝚗𝚝 (\geq (𝚅𝙰𝚁 1)), \neq, 𝚊𝚕𝚕, 𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎)$ has a similar explanation.
We now present two examples related to the $𝚔_𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝$ constraint. The first example illustrates the fact that the path specifying the scope of the exchange can contain more than one collection. The second example exemplifies the fact that the path specifying the scope of the exchange does not necessarily start with a top level collection.
EXAMPLE 10: Consider the $𝚔_𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝$ $(𝚂𝙴𝚃𝚂)$ constraint which, given $| 𝚂𝙴𝚃𝚂 |$ sets of domain variables, forces that no value is assigned to more than one set. Note that we can swap all the occurrences of two values, or replace all occurrences of a value by a value that is not yet used. Within the electronic catalogue this is represented by the following meta-data, $𝚟𝚊𝚕𝚜 ([𝚂𝙴𝚃𝚂 . 𝚜𝚎𝚝 . 𝚟𝚊𝚛], 𝚒𝚗𝚝, \neq, 𝚊𝚕𝚕, 𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎)$ , to which corresponds the following textual form:

All occurrences of two distinct values of $𝚂𝙴𝚃𝚂 . 𝚜𝚎𝚝 . 𝚟𝚊𝚛$ can be swapped; all occurrences of a value of $𝚂𝙴𝚃𝚂 . 𝚜𝚎𝚝 . 𝚟𝚊𝚛$ can be renamed to any unused value.

For instance, since $𝚔_𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝$ $(〈 𝚜𝚎𝚝 - 〈 1, 9, 1, 5 〉, 𝚜𝚎𝚝 - 〈 7, 2, 7 〉 〉)$ is a solution, we can replace value 1 by any value that is different from the already used values 2, 5, 7, and 9, e.g. value 3, and get another valid solution $𝚔_𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝$ $(〈 𝚜𝚎𝚝 - 〈 3, 9, 3, 5 〉, 𝚜𝚎𝚝 - 〈 7, 2, 7 〉 〉)$ . From the solution $𝚔_𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝$ $(〈 𝚜𝚎𝚝 - 〈 1, 9, 1, 5 〉, 𝚜𝚎𝚝 - 〈 7, 2, 7 〉 〉)$ , we can also swap all occurrences of two values, e.g. values 1 and 2, and get another valid solution $𝚔_𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝$ $(〈 𝚜𝚎𝚝 - 〈 2, 9, 2, 5 〉, 𝚜𝚎𝚝 - 〈 7, 1, 7 〉 〉)$ .

The five parameters of $𝚟𝚊𝚕𝚜 ([𝚂𝙴𝚃𝚂 . 𝚜𝚎𝚝 . 𝚟𝚊𝚛], 𝚒𝚗𝚝, \neq, 𝚊𝚕𝚕, 𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎)$ have the following meaning:
- $[𝚂𝙴𝚃𝚂 . 𝚜𝚎𝚝 . 𝚟𝚊𝚛]$ indicates that the modification takes place within the values assigned to the $𝚟𝚊𝚛$ attribute of the $𝚂𝙴𝚃𝚂 . 𝚜𝚎𝚝$ collections.
- $𝚒𝚗𝚝$ defines the partition of values $𝒫 = \dots, {- 1}, {0}, {1}, \dots$ .
- $\neq$ indicates that the exchange of values takes place between two distinct elements of $𝒫$ .
- $𝚊𝚕𝚕$ specifies that all occurrences of the source value have to be exchanged with all occurrences of the target value.
- $𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎$ tells that the source value can be replaced by an already existing value or by a new value, i.e., a value not already used in $𝚂𝙴𝚃𝚂 . 𝚜𝚎𝚝 . 𝚟𝚊𝚛$ .
EXAMPLE 11: Consider the $𝚔_𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝$ $(𝚂𝙴𝚃𝚂)$ constraint which, given $| 𝚂𝙴𝚃𝚂 |$ sets of domain variables, forces that no value is assigned to more than one set. Note that, within any set, we can replace any occurrence of a value by another value that is already used in the same set. Within the electronic catalogue this is represented by the following meta-data, $𝚟𝚊𝚕𝚜 ([𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛], 𝚒𝚗𝚝, \neq, 𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎, 𝚒𝚗)$ , to which corresponds the following textual form:

An occurrence of a value of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ can be replaced by any value of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ .

For instance, since $𝚔_𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝$ $(〈 𝚜𝚎𝚝 - 〈 1, 9, 1, 5 〉, 𝚜𝚎𝚝 - 〈 7, 2, 7 〉 〉)$ is a solution, we can replace within the first set the first occurrence of value 1 by the already used value 5, and get another valid solution $𝚔_𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝$ $(〈 𝚜𝚎𝚝 - 〈 5, 9, 1, 5 〉, 𝚜𝚎𝚝 - 〈 7, 2, 7 〉 〉)$ .

The five parameters of $𝚟𝚊𝚕𝚜 ([𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛], 𝚒𝚗𝚝, \neq, 𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎, 𝚒𝚗)$ have the following meaning:
- $[𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛]$ indicates that the modification takes place within the values assigned to the $𝚟𝚊𝚛$ attribute of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ collections. Note that since the corresponding path does not start from a top level collection (i.e., $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ does not correspond to an argument of the $𝚔_𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝$ constraint), this represents one set of values for each set: the scope of value symmetry is located within a single set.
- $𝚒𝚗𝚝$ defines the partition of values $𝒫 = \dots, {- 1}, {0}, {1}, \dots$ .
- $\neq$ indicates that the exchange of values takes place between two distinct elements of $𝒫$ .
- $𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎$ specifies that one occurrence of the source value has to be replaced by the target value.
- $𝚒𝚗$ tells that the source value has to be replaced by an already existing value in $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ .
We present a last example where the path specifying the scope of the exchange does not end with an attribute but rather with a collection. This can be seen as a generalisation of value symmetry where, instead of exchanging values, we exchange tuples of values. This kind of value symmetry occurs in constraints like $𝚌𝚘𝚗𝚍_𝚕𝚎𝚡_𝚌𝚘𝚜𝚝$ , $𝚒𝚗_𝚛𝚎𝚕𝚊𝚝𝚒𝚘𝚗$ , $𝚗𝚙𝚊𝚒𝚛$ , $𝚗𝚟𝚎𝚌𝚝𝚘𝚛$ , $𝚗𝚟𝚎𝚌𝚝𝚘𝚛𝚜$ , or $𝚙𝚊𝚝𝚝𝚎𝚛𝚗$ .
EXAMPLE 12: Consider the $𝚗𝚟𝚎𝚌𝚝𝚘𝚛$ $(𝙽𝚅𝙴𝙲, 𝚅𝙴𝙲𝚃𝙾𝚁𝚂)$ constraint which forces an equality between $𝙽𝚅𝙴𝙲$ and the number of distinct tuples of values taken by the vectors of the collection $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ . Note that we can swap all the occurrences of two tuples of values, or replace all occurrences of a tuple of values by a tuple of values that is not yet used. Within the electronic catalogue this is represented by the following meta-data, $𝚟𝚊𝚕𝚜 ([𝚅𝙴𝙲𝚃𝙾𝚁𝚂 . 𝚟𝚎𝚌], 𝚒𝚗𝚝, \neq, 𝚊𝚕𝚕, 𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎)$ , to which corresponds the following textual form:

All occurrences of two distinct tuples of values of $𝚅𝙴𝙲𝚃𝙾𝚁𝚂 . 𝚟𝚎𝚌$ can be swapped; all occurrences of a tuple of values of $𝚅𝙴𝙲𝚃𝙾𝚁𝚂 . 𝚟𝚎𝚌$ can be renamed to any unused tuple of values.

For instance, since $𝚗𝚟𝚎𝚌𝚝𝚘𝚛$ $(2, 〈 𝚟𝚎𝚌 - 〈 5, 6 〉, 𝚟𝚎𝚌 - 〈 9, 2 〉, 𝚟𝚎𝚌 - 〈 5, 6 〉 〉)$ is a solution, we can replace all the occurrences of the tuple of values $〈 5, 6 〉$ by any unused tuple of values, e.g. the tuple of values $〈 1, 2 〉$ , and get another valid solution $𝚗𝚟𝚎𝚌𝚝𝚘𝚛$ $(2, 〈 𝚟𝚎𝚌 - 〈 1, 2 〉, 𝚟𝚎𝚌 - 〈 9, 2 〉, 𝚟𝚎𝚌 - 〈 1, 2 〉 〉)$ .

The five parameters of $𝚟𝚊𝚕𝚜 ([𝚅𝙴𝙲𝚃𝙾𝚁𝚂 . 𝚟𝚎𝚌], 𝚒𝚗𝚝, \neq, 𝚊𝚕𝚕, 𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎)$ have the following meaning:
- $[𝚅𝙴𝙲𝚃𝙾𝚁𝚂 . 𝚟𝚎𝚌]$ indicates that the modification takes place within the tuples of values assigned to the $𝚟𝚎𝚌$ attribute of the $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ collections.
- $𝚒𝚗𝚝$ defines the partition of values $𝒫 = ℤ^{| 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 |}$ .
- $\neq$ indicates that the exchange of tuple of values takes place between two distinct elements of $𝒫$ .
- $𝚊𝚕𝚕$ specifies that all occurrences of the source tuple of values have to be exchanged with all occurrences of the target tuple of values.
- $𝚍𝚘𝚗𝚝𝚌𝚊𝚛𝚎$ tells that the source tuple of values can be replaced by an already existing tuple of values or by a new tuple of values, i.e., a tuple of values not already used in $𝚅𝙴𝙲𝚃𝙾𝚁𝚂 . 𝚟𝚎𝚌$ .
$𝚝𝚛𝚊𝚗𝚜𝚕𝚊𝚝𝚎 (𝙰𝚃𝚃𝚁𝙸𝙱𝚄𝚃𝙴𝚂)$ denotes the fact that we add a constant to some collection attributes (i.e., we express the fact that solutions are preserved under some specific translation). $𝙰𝚃𝚃𝚁𝙸𝙱𝚄𝚃𝙴𝚂$ is a list of terms of the form $𝙰𝚁𝙶 1$ , or $𝙰𝚁𝙶 2 . 𝚊𝚝𝚝𝚛$ , or $𝙰𝚁𝙶 3 . {𝚊𝚝𝚝𝚛}_{𝚒} . {𝚊𝚝𝚝𝚛}_{𝚓}$ , where:
- $𝙰𝚁𝙶 1$ is an argument of the global constraint of type domain variable or integer.
- $𝙰𝚁𝙶 2$ is an argument of the global constraint that corresponds to a collection, and $𝚊𝚝𝚝𝚛$ is an attribute of $𝙰𝚁𝙶 2$ of type domain variable or integer.
- $𝙰𝚁𝙶 3$ is an argument of the global constraint that corresponds to a collection, and ${𝚊𝚝𝚝𝚛}_{𝚒}$ is an attribute of $𝙰𝚁𝙶 3$ of type collection, and ${𝚊𝚝𝚝𝚛}_{𝚓}$ is an attribute of $𝙰𝚁𝙶 3 . {𝚊𝚝𝚝𝚛}_{𝚒}$ of type domain variable or integer.
Its purpose is to define all the elements that have to be simultaneously incremented by one and the same constant.
- The case corresponding to $𝙰𝚁𝙶 1$ is motivated by the fact that we sometimes want to increment an argument that is a domain variable or an integer.
- The case corresponding to $𝙰𝚁𝙶 2 . 𝚊𝚝𝚝𝚛$ is the standard case where we want to express that we increment attribute $𝚊𝚝𝚝𝚛$ of all items of a collection that is passed as an argument of the global constraint.
- Finally, the last case $𝙰𝚁𝙶 3 . {𝚊𝚝𝚝𝚛}_{𝚒} . {𝚊𝚝𝚝𝚛}_{𝚓}$ corresponds to the fact that we want to increment attribute ${𝚊𝚝𝚝𝚛}_{𝚓}$ of all items corresponding to $𝙰𝚁𝙶 3 . {𝚊𝚝𝚝𝚛}_{𝚒}$ .

We now provide two examples, where the translation is respectively applied on a single attribute and on two attributes of a collection.

EXAMPLE 1: Consider the $𝚊𝚕𝚕_𝚖𝚒𝚗_𝚍𝚒𝚜𝚝$ $(𝙼𝙸𝙽𝙳𝙸𝚂𝚃, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$ constraint which forces for each pair $({𝚟𝚊𝚛}_{i}, {𝚟𝚊𝚛}_{j})$ of distinct variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ that $| {𝚟𝚊𝚛}_{i} - {𝚟𝚊𝚛}_{j} | \geq 𝙼𝙸𝙽𝙳𝙸𝚂𝚃$ . Note that we can add one and the same constant to all variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ since this does not change the difference between any pair of variables. Within the electronic catalogue this is represented by the following meta-data, $𝚝𝚛𝚊𝚗𝚜𝚕𝚊𝚝𝚎 ([𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛])$ , to which corresponds the following textual form:

One and the same constant can be added to the $𝚟𝚊𝚛$ attribute of all items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

For instance, since $𝚊𝚕𝚕_𝚖𝚒𝚗_𝚍𝚒𝚜𝚝$ $(2, 〈 5, 1, 9, 3 〉)$ is a solution, we can add the constant 6 to all items of the collection $〈 5, 1, 9, 3 〉$ , and get another valid solution $𝚊𝚕𝚕_𝚖𝚒𝚗_𝚍𝚒𝚜𝚝$ $(2, 〈 11, 7, 15, 9 〉)$ .

EXAMPLE 2: Consider the $𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎$ $(𝚃𝙰𝚂𝙺𝚂, 𝙻𝙸𝙼𝙸𝚃)$ constraint which forces that at each point in time, the cumulated height of the set of tasks that overlap that point, does not exceed a given limit. Note that we can add one and the same constant to all $𝚘𝚛𝚒𝚐𝚒𝚗$ and $𝚎𝚗𝚍$ attributes of the different tasks of the $𝚃𝙰𝚂𝙺𝚂$ collection. This operation simply shifts the overall schedule by a given constant without affecting the maximum resource consumption. Within the electronic catalogue this is represented by the following meta-data, $𝚝𝚛𝚊𝚗𝚜𝚕𝚊𝚝𝚎 ([𝚃𝙰𝚂𝙺𝚂 . 𝚘𝚛𝚒𝚐𝚒𝚗, 𝚃𝙰𝚂𝙺𝚂 . 𝚎𝚗𝚍])$ , to which corresponds the following textual form:

One and the same constant can be added to the $𝚘𝚛𝚒𝚐𝚒𝚗$ and $𝚎𝚗𝚍$ attributes of all items of $𝚃𝙰𝚂𝙺𝚂$ .

For instance, since

(\begin{matrix} 〈\begin{matrix} 𝚘𝚛𝚒𝚐𝚒𝚗 - 1 & 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 3 & 𝚎𝚗𝚍 - 4 & 𝚑𝚎𝚒𝚐𝚑𝚝 - 1, \\ 𝚘𝚛𝚒𝚐𝚒𝚗 - 2 & 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 9 & 𝚎𝚗𝚍 - 11 & 𝚑𝚎𝚒𝚐𝚑𝚝 - 2, \\ 𝚘𝚛𝚒𝚐𝚒𝚗 - 3 & 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 10 & 𝚎𝚗𝚍 - 13 & 𝚑𝚎𝚒𝚐𝚑𝚝 - 1, \\ 𝚘𝚛𝚒𝚐𝚒𝚗 - 6 & 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 6 & 𝚎𝚗𝚍 - 12 & 𝚑𝚎𝚒𝚐𝚑𝚝 - 1, \\ 𝚘𝚛𝚒𝚐𝚒𝚗 - 7 & 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 2 & 𝚎𝚗𝚍 - 9 & 𝚑𝚎𝚒𝚐𝚑𝚝 - 3 \end{matrix}〉, 8 \end{matrix})

is a solution, we can add the constant 2 to all $𝚘𝚛𝚒𝚐𝚒𝚗$ and $𝚎𝚗𝚍$ attributes, and get another valid solution

(\begin{matrix} 〈\begin{matrix} 𝚘𝚛𝚒𝚐𝚒𝚗 - 3 & 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 3 & 𝚎𝚗𝚍 - 6 & 𝚑𝚎𝚒𝚐𝚑𝚝 - 1, \\ 𝚘𝚛𝚒𝚐𝚒𝚗 - 4 & 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 9 & 𝚎𝚗𝚍 - 13 & 𝚑𝚎𝚒𝚐𝚑𝚝 - 2, \\ 𝚘𝚛𝚒𝚐𝚒𝚗 - 5 & 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 10 & 𝚎𝚗𝚍 - 15 & 𝚑𝚎𝚒𝚐𝚑𝚝 - 1, \\ 𝚘𝚛𝚒𝚐𝚒𝚗 - 8 & 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 6 & 𝚎𝚗𝚍 - 14 & 𝚑𝚎𝚒𝚐𝚑𝚝 - 1, \\ 𝚘𝚛𝚒𝚐𝚒𝚗 - 9 & 𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗 - 2 & 𝚎𝚗𝚍 - 11 & 𝚑𝚎𝚒𝚐𝚑𝚝 - 3 \end{matrix}〉, 8 \end{matrix}) .

We conclude by listing other types of symmetries that we may also consider in the future, namely:

In the context of graph constraints we can usually relabel the vertices of the corresponding graph. This is for instance the case of the $𝚌𝚒𝚛𝚌𝚞𝚒𝚝$ constraint where the $𝚒𝚗𝚍𝚎𝚡$ attribute corresponds to the name of a vertex.
In the context of constraints on a matrix we can have symmetries on both the rows and the columns of the matrix. On the one hand, since a row corresponds to a collection this can be currently expressed. On the other hand, since a column corresponds to all the $i^{t h}$ items of the collections corresponding to the rows, this currently cannot be expressed.
Given a collection of items, we want to express a symmetry on different subsets of items: more precisely, on all items for which a given attribute is assigned the same value. As an illustrative example consider the $𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎𝚜$ constraint. We would like to express the possibility of translating the origin of all tasks that are assigned the same machine.
Given a collection of items we can sometimes multiply by $- 1$ all occurrences of one of its attributes. This usually corresponds to a mirror symmetry. This is for instance the case for the $𝚘𝚛𝚒𝚐𝚒𝚗$ attribute of the $𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎$ constraint.

Global Constraint Catalog

2. Describing Global Constraints

2.2.5. Describing symmetries between arguments