2.1.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:

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, enforces 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 if 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, enforces 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],...,๐™ฐ๐š๐™ถ[m]โŒช, a permutation of ๐™ฟ๐™ด๐š๐™ผ๐š„๐šƒ๐™ฐ๐šƒ๐™ธ๐™พ๐™ฝ๐š‚, not necessarily the same, is applied on the items of a subset of the set of collections {๐™ฐ๐š๐™ถ[1].๐šŠ๐š๐š๐š›,๐™ฐ๐š๐™ถ[2].๐šŠ๐š๐š๐š›,...,๐™ฐ๐š๐™ถ[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 fact that we use 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 ,...,e n to e n ,e n-1 ,...,e 1 .

      3. ๐šœ๐š‘๐š’๐š๐š stands for the set that only contains the permutation that maps the sequence e 1 ,e 2 ,...,e n to e n ,e 1 ,...,e n-1 .

    EXAMPLEย 1: As a first example, consider the ๐šŠ๐š•๐š•๐š๐š’๐š๐š๐šŽ๐š›๐šŽ๐š—๐š(๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚) constraint, which has one 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 of the ๐šŠ๐š•๐š•๐š๐š’๐š๐š๐šŽ๐š›๐šŽ๐š—๐š constraint.

    EXAMPLEย 2: As a second example, consider the ๐š”_๐šœ๐šŠ๐š–๐šŽ(๐š‚๐™ด๐šƒ๐š‚) constraint, which has one 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.,ย ๐š”_๐šœ๐šŠ๐š–๐šŽ enforces an equality between multisets). The argument ๐š‚๐™ด๐šƒ๐š‚ is a collection, where each item consists of one 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.:

  • ๐š’๐š๐šŽ๐š–๐šœ_๐šœ๐šข๐š—๐šŒ(๐™ฒ๐™พ๐™ป๐™ป๐™ด๐™ฒ๐šƒ๐™ธ๐™พ๐™ฝ๐š‚,๐™ฟ๐™ด๐š๐™ผ๐š„๐šƒ๐™ฐ๐šƒ๐™ธ๐™พ๐™ฝ๐š‚) 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 one single element then this element has the form ๐™ฐ๐š๐™ถ.๐šŠ๐š๐š๐š›. This stems from the fact that we want to designate more than one 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 ,...,e n to e n ,e n-1 ,...,e 1 .

      3. ๐šœ๐š‘๐š’๐š๐š stands for the set that only contains the permutation that maps the sequence e 1 ,e 2 ,...,e n to e n ,e 1 ,...,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].๐š—๐š‹, ..., ๐™ถ๐š๐™พ๐š„๐™ฟ_๐š‚๐™ธ๐š‰๐™ด๐š‚[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 reversable.

    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 enforces ๐™ฝ๐š…๐™ด๐™ฒ 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.:

  • ๐šŠ๐š๐š๐š›๐šœ(๐™ฒ๐™พ๐™ป๐™ป๐™ด๐™ฒ๐šƒ๐™ธ๐™พ๐™ฝ,๐™ฟ๐™ด๐š๐™ผ๐š„๐šƒ๐™ฐ๐šƒ๐™ธ๐™พ๐™ฝ) 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 enforces 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 enforces ๐™ฝ๐™ฒ๐š๐™พ๐š‚๐š‚ 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 parameterized by five parameters:
    • ๐™ฐ๐šƒ๐šƒ๐š๐™ธ๐™ฑ๐š„๐šƒ๐™ด๐š‚ is a list of paths of the form ๐™ฐ๐š๐™ถ0 or ๐™ฐ๐š๐™ถ1.โ‹ฏ.๐™ฐ๐š๐™ถ๐š—.๐šŠ๐š๐š๐š› (nโ‰ฅ1), where:

      • ๐™ฐ๐š๐™ถ0 is an argument of the global constraint of type domain variable, integer, or collection of domain variables or integers.

      • ๐™ฐ๐š๐™ถ1.โ‹ฏ.๐™ฐ๐š๐™ถ๐š—.๐šŠ๐š๐š๐š› 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 is motivated by the fact that we sometimes want to express the fact that the value of an integer argument can be changed in such a way that we preserve the fact that we still have a solution.

      • The case when ๐™ฐ๐š๐™ถ1 is not a top level collection is motivated by the fact that we sometimes want 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.โ‹ฏ.๐™ฐ๐š๐™ถ๐š—.๐šŠ๐š๐š๐š› is a path to a collection of variables or integers allows expressing swap between tuples of values (i.e.,ย the exchange of values is generalized to the exchange of tuples of values).

    • ๐™ฟ๐™ฐ๐š๐šƒ๐™ธ๐šƒ๐™ธ๐™พ๐™ฝ usually defines a partition ๐’ซ of integer values. Only when ๐™ฐ๐š๐™ถ1.โ‹ฏ.๐™ฐ๐š๐™ถ๐š—.๐šŠ๐š๐š๐š› 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}.

        • ๐‘๐‘š๐‘(๐šž), (๐‘๐‘š๐‘โˆˆ{=,โ‰ ,<,โ‰ฅ,>,โ‰ค}), denotes the set of all integers e such that the comparison e ๐‘๐‘š๐‘ u holds.

        • ๐š’๐š—(u,v), (uโ‰คv), denotes the set of all integers located in interval [u,v].

        • ๐š—๐š˜๐š๐š’๐š—(u,v), (uโ‰คv), denotes the set of all integers not located in interval [u,v].

        • ๐š–๐š˜๐š(u,v), (0<v<u,u,vโˆˆโ„• + ), denotes all integer values in โ„ค that have v as remainder when divided by u.remainder(a,n)=a-nโŒŠa nโŒ‹.

      • Given set of values generators ๐’ฎ 1 , ๐’ฎ 2 , ..., ๐’ฎ n (nโ‰ฅ2), a compound set of values generator is defined by:

        • [๐’ฎ 1 ,๐’ฎ 2 ,...,๐’ฎ n ] denotes all values that are in at least one of the sets ๐’ฎ 1 , ๐’ฎ 2 , ..., ๐’ฎ n .

        • ๐š—๐š˜๐š๐š’๐š—([๐’ฎ 1 ,๐’ฎ 2 ,...,๐’ฎ n ]) denotes all values of โ„ค that are not in any set ๐’ฎ 1 , ๐’ฎ 2 , ..., ๐’ฎ 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 one single class of values corresponding to all integer values in โ„ค.

      • ๐šŠ๐š•๐š•(๐’ฎ) denotes a partition ๐’ซ containing one 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ยทu,kยทu+u-1], kโˆˆโ„ค.

      • ๐š–๐š˜๐š(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โŒŠ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 occurrence 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 โ‰ , =, <, โ‰ฅ, >, โ‰ค, or ๐š๐š˜๐š—๐š๐šŒ๐šŠ๐š›๐šŽ. It specifies a set of pairs {(p i 1 ,p j 1 ),(p i 2 ,p j 2 ),...,(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โˆˆ[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โˆˆ[1,n]), such that uโˆˆp i k and vโˆˆ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. Given,

      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 ,...,๐’ฑ 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 ),...,(p i n ,p j n )} of elements of the partition ๐’ซ such that the condition ๐™ฟ๐™ฐ๐™ธ๐š๐š‚=๐š๐š˜๐š—๐š๐šŒ๐šŠ๐š›๐šŽโˆจi k ๐™ฟ๐™ฐ๐™ธ๐š๐š‚ j k holds for all kโˆˆ[1,n],

      6. a ๐šƒ๐™ฐ๐š๐™ถ๐™ด๐šƒ option,

      given one of the sets of values ๐’ฑ ฮฑ , (1โ‰คฮฑโ‰ค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โ‰ v (source and target values should be distinct),

      2. uโˆˆ๐’ฑ ฮฑ (source value, i.e.,ย value that is replaced, should be part of the solution),

      3. โˆƒk|uโˆˆp i k โˆงvโˆˆp j k (source and target values should be located in the appropriate partition classes),

      4. ๐šƒ๐™ฐ๐š๐™ถ๐™ด๐šƒ=๐š’๐š—โ‡’vโˆˆ๐’ฑ ฮฑ (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 enforces 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, ๐šŸ๐šŠ๐š•๐šœ([๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚.๐šŸ๐šŠ๐š›],๐š’๐š—๐š,โ‰ ,๐šŠ๐š•๐š•,๐š๐š˜๐š—๐š๐šŒ๐šŠ๐š›๐šŽ), 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 ๐šŸ๐šŠ๐š•๐šœ([๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚.๐šŸ๐šŠ๐š›],๐š’๐š—๐š,โ‰ ,๐šŠ๐š•๐š•,๐š๐š˜๐š—๐š๐šŒ๐šŠ๐š›๐šŽ) 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 ๐’ซ=...,{-1},{0},{1},...ย .

    • โ‰  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 enforces ๐™ฝ๐š…๐™ฐ๐™ป 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, ๐šŸ๐šŠ๐š•๐šœ([๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚.๐šŸ๐šŠ๐š›],๐š’๐š—๐š,โ‰ ,๐šŠ๐š•๐š•,๐š๐š˜๐š—๐š๐šŒ๐šŠ๐š›๐šŽ), 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 ๐šŸ๐šŠ๐š•๐šœ([๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚.๐šŸ๐šŠ๐š›],๐š’๐š—๐š,โ‰ ,๐šŠ๐š•๐š•,๐š๐š˜๐š—๐š๐šŒ๐šŠ๐š›๐šŽ) 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 ๐’ซ=...,{-1},{0},{1},...ย .

    • โ‰  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, ๐šŸ๐šŠ๐š•๐šœ([๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚.๐šŸ๐šŠ๐š›],๐š’๐š—๐š,โ‰ ,๐šŠ๐š•๐š•,๐š๐š˜๐š—๐š๐šŒ๐šŠ๐š›๐šŽ), is replaced by ๐šŸ๐šŠ๐š•๐šœ([๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚.๐šŸ๐šŠ๐š›],๐š’๐š—๐š,โ‰ ,๐šŠ๐š•๐š•,๐š’๐š—), i.e.,ย we are not allowed to introduce an unused value.

    EXAMPLEย 3: As a third example, consider the ๐šŠ๐š•๐š•_๐š–๐š’๐š—_๐š๐š’๐šœ๐š(๐™ผ๐™ธ๐™ฝ๐™ณ๐™ธ๐š‚๐šƒ, ๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚) constraint, which enforces for each pair (๐šŸ๐šŠ๐š› i ,๐šŸ๐šŠ๐š› j ) of distinct variables of the collection ๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚ that |๐šŸ๐šŠ๐š› i -๐šŸ๐šŠ๐š› j |โ‰ฅ๐™ผ๐™ธ๐™ฝ๐™ณ๐™ธ๐š‚๐šƒ. 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, ๐šŸ๐šŠ๐š•๐šœ([๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚.๐šŸ๐šŠ๐š›],๐š’๐š—๐š,โ‰ ,๐šŠ๐š•๐š•,๐š’๐š—), 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 ๐šŸ๐šŠ๐š•๐šœ([๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚.๐šŸ๐šŠ๐š›],๐š’๐š—๐š,โ‰ ,๐šŠ๐š•๐š•,๐š’๐š—) 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 ๐’ซ=...,{-1},{0},{1},...ย .

    • โ‰  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 enforces ๐™ผ๐™ธ๐™ฝ 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, ๐šŸ๐šŠ๐š•๐šœ([๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚.๐šŸ๐šŠ๐š›],๐š’๐š—๐š,โ‰ ,๐šŠ๐š•๐š•,๐š’๐š—), 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 ๐šŸ๐šŠ๐š•๐šœ([๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚.๐šŸ๐šŠ๐š›],๐š’๐š—๐š,โ‰ ,๐šŠ๐š•๐š•,๐š’๐š—) 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 ๐’ซ=...,{-1},{0},{1},...ย .

    • โ‰  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 enforces ๐™ฝ๐š…๐™ฐ๐š 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 enforces 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, ๐šŸ๐šŠ๐š•๐šœ([๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚.๐šŸ๐šŠ๐š›],๐šŒ๐š˜๐š–๐š™(๐š…๐™ฐ๐™ป๐š„๐™ด),โ‰ฅ,๐š๐š˜๐š—๐š๐šŒ๐šŠ๐š›๐šŽ,๐š๐š˜๐š—๐š๐šŒ๐šŠ๐š›๐šŽ), 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 ๐šŸ๐šŠ๐š•๐šœ([๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚.๐šŸ๐šŠ๐š›],๐šŒ๐š˜๐š–๐š™(๐š…๐™ฐ๐™ป๐š„๐™ด),โ‰ฅ,๐š๐š˜๐š—๐š๐šŒ๐šŠ๐š›๐šŽ, ๐š๐š˜๐š—๐š๐šŒ๐šŠ๐š›๐šŽ) 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 ๐š…๐™ฐ๐™ป๐š„๐™ด.

    • โ‰ฅ indicates that the the source and target values should respectively belong to sets ๐’ฎ i and ๐’ฎ j where iโ‰ฅ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 enforces 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, ๐šŸ๐šŠ๐š•๐šœ([๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚.๐šŸ๐šŠ๐š›],๐šŒ๐š˜๐š–๐š™(๐š…๐™ฐ๐™ป๐š„๐™ด),โ‰ค,๐š๐š˜๐š—๐š๐šŒ๐šŠ๐š›๐šŽ,๐š๐š˜๐š—๐š๐šŒ๐šŠ๐š›๐šŽ), 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 ๐šŸ๐šŠ๐š•๐šœ([๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚.๐šŸ๐šŠ๐š›],๐šŒ๐š˜๐š–๐š™(๐š…๐™ฐ๐™ป๐š„๐™ด),โ‰ค,๐š๐š˜๐š—๐š๐šŒ๐šŠ๐š›๐šŽ, ๐š๐š˜๐š—๐š๐šŒ๐šŠ๐š›๐šŽ) 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 ๐š…๐™ฐ๐™ป๐š„๐™ด.

    • โ‰ค indicates that the the source and target values should respectively belong to sets ๐’ฎ i and ๐’ฎ j where iโ‰ค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 enforces 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.๐šŸ๐šŠ๐š›],๐š’๐š—๐š,โ‰ ,๐šŠ๐š•๐š•,๐š๐š˜๐š—๐š๐šŒ๐šŠ๐š›๐šŽ), 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.๐šŸ๐šŠ๐š›],๐š’๐š—๐š,โ‰ ,๐šŠ๐š•๐š•, ๐š๐š˜๐š—๐š๐šŒ๐šŠ๐š›๐šŽ) 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 ๐’ซ=...,{-1},{0},{1},...ย .

    • โ‰  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 enforces ๐š…๐™ฐ๐š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],๐š’๐š—๐š(โ‰ค(๐š…๐™ฐ๐š2)),โ‰ ,๐šŠ๐š•๐š•,๐š๐š˜๐š—๐š๐šŒ๐šŠ๐š›๐šŽ) and ๐šŸ๐šŠ๐š•๐šœ([๐š…๐™ฐ๐š2],๐š’๐š—๐š(โ‰ฅ(๐š…๐™ฐ๐š1)),โ‰ ,๐šŠ๐š•๐š•,๐š๐š˜๐š—๐š๐šŒ๐šŠ๐š›๐šŽ), to which corresponds the following textual form:

    ย ย ย ย ๐š…๐™ฐ๐š1 can be replaced by any value โ‰ค ๐š…๐™ฐ๐š2;

    ย ย ย ย ๐š…๐™ฐ๐š2 can be replaced by any value โ‰ฅ ๐š…๐™ฐ๐š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],๐š’๐š—๐š(โ‰ค(๐š…๐™ฐ๐š2)),โ‰ ,๐šŠ๐š•๐š•,๐š๐š˜๐š—๐š๐šŒ๐šŠ๐š›๐šŽ) have the following meaning:

    • [๐š…๐™ฐ๐š1] indicates that the modification takes place within the value assigned to the argument ๐š…๐™ฐ๐š1 of the constraint ๐š•๐šŽ๐šš.

    • ๐š’๐š—๐š(โ‰ค(๐š…๐™ฐ๐š2)) defines the partition of values ๐’ซ=...,{๐š…๐™ฐ๐š2-2},{๐š…๐™ฐ๐š2-1},{๐š…๐™ฐ๐š2} (i.e.,ย we only consider values that are less than or equal to ๐š…๐™ฐ๐š2).

    • โ‰  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 one 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],๐š’๐š—๐š(โ‰ฅ(๐š…๐™ฐ๐š1)),โ‰ ,๐šŠ๐š•๐š•,๐š๐š˜๐š—๐š๐šŒ๐šŠ๐š›๐šŽ) 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, enforces 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, ๐šŸ๐šŠ๐š•๐šœ([๐š‚๐™ด๐šƒ๐š‚.๐šœ๐šŽ๐š.๐šŸ๐šŠ๐š›],๐š’๐š—๐š,โ‰ ,๐šŠ๐š•๐š•,๐š๐š˜๐š—๐š๐šŒ๐šŠ๐š›๐šŽ), 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 ๐šŸ๐šŠ๐š•๐šœ([๐š‚๐™ด๐šƒ๐š‚.๐šœ๐šŽ๐š.๐šŸ๐šŠ๐š›],๐š’๐š—๐š,โ‰ ,๐šŠ๐š•๐š•,๐š๐š˜๐š—๐š๐šŒ๐šŠ๐š›๐šŽ) 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 ๐’ซ=...,{-1},{0},{1},...ย .

    • โ‰  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, enforces 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, ๐šŸ๐šŠ๐š•๐šœ([๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚.๐šŸ๐šŠ๐š›],๐š’๐š—๐š,โ‰ ,๐š๐š˜๐š—๐š๐šŒ๐šŠ๐š›๐šŽ,๐š’๐š—), 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 ๐šŸ๐šŠ๐š•๐šœ([๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚.๐šŸ๐šŠ๐š›],๐š’๐š—๐š,โ‰ ,๐š๐š˜๐š—๐š๐šŒ๐šŠ๐š›๐šŽ,๐š’๐š—) 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 one single set.

    • ๐š’๐š—๐š defines the partition of values ๐’ซ=...,{-1},{0},{1},...ย .

    • โ‰  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 enforces 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, ๐šŸ๐šŠ๐š•๐šœ([๐š…๐™ด๐™ฒ๐šƒ๐™พ๐š๐š‚.๐šŸ๐šŽ๐šŒ],๐š’๐š—๐š,โ‰ ,๐šŠ๐š•๐š•,๐š๐š˜๐š—๐š๐šŒ๐šŠ๐š›๐šŽ), 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 ๐šŸ๐šŠ๐š•๐šœ([๐š…๐™ด๐™ฒ๐šƒ๐™พ๐š๐š‚.๐šŸ๐šŽ๐šŒ],๐š’๐š—๐š,โ‰ ,๐šŠ๐š•๐š•,๐š๐š˜๐š—๐š๐šŒ๐šŠ๐š›๐šŽ) 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 ๐’ซ=โ„ค |๐š…๐™ด๐™ฒ๐šƒ๐™พ๐š๐š‚| .

    • โ‰  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 one single attribute and on two attributes of a collection.

EXAMPLEย 1: Consider the ๐šŠ๐š•๐š•_๐š–๐š’๐š—_๐š๐š’๐šœ๐š(๐™ผ๐™ธ๐™ฝ๐™ณ๐™ธ๐š‚๐šƒ,๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚) constraint which enforces for each pair (๐šŸ๐šŠ๐š› i ,๐šŸ๐šŠ๐š› j ) of distinct variables of the collection ๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚ that |๐šŸ๐šŠ๐š› i -๐šŸ๐šŠ๐š› j |โ‰ฅ๐™ผ๐™ธ๐™ฝ๐™ณ๐™ธ๐š‚๐šƒ. 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 enforces 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

๐š˜๐š›๐š’๐š๐š’๐š—-1๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-3๐šŽ๐š—๐š-4๐š‘๐šŽ๐š’๐š๐š‘๐š-1,๐š˜๐š›๐š’๐š๐š’๐š—-2๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-9๐šŽ๐š—๐š-11๐š‘๐šŽ๐š’๐š๐š‘๐š-2,๐š˜๐š›๐š’๐š๐š’๐š—-3๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-10๐šŽ๐š—๐š-13๐š‘๐šŽ๐š’๐š๐š‘๐š-1,๐š˜๐š›๐š’๐š๐š’๐š—-6๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-6๐šŽ๐š—๐š-12๐š‘๐šŽ๐š’๐š๐š‘๐š-1,๐š˜๐š›๐š’๐š๐š’๐š—-7๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-2๐šŽ๐š—๐š-9๐š‘๐šŽ๐š’๐š๐š‘๐š-3,8

is a solution, we can add the constant 2 to all ๐š˜๐š›๐š’๐š๐š’๐š— and ๐šŽ๐š—๐š attributes, and get another valid solution

๐š˜๐š›๐š’๐š๐š’๐š—-3๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-3๐šŽ๐š—๐š-6๐š‘๐šŽ๐š’๐š๐š‘๐š-1,๐š˜๐š›๐š’๐š๐š’๐š—-4๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-9๐šŽ๐š—๐š-13๐š‘๐šŽ๐š’๐š๐š‘๐š-2,๐š˜๐š›๐š’๐š๐š’๐š—-5๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-10๐šŽ๐š—๐š-15๐š‘๐šŽ๐š’๐š๐š‘๐š-1,๐š˜๐š›๐š’๐š๐š’๐š—-8๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-6๐šŽ๐š—๐š-14๐š‘๐šŽ๐š’๐š๐š‘๐š-1,๐š˜๐š›๐š’๐š๐š’๐š—-9๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—-2๐šŽ๐š—๐š-11๐š‘๐šŽ๐š’๐š๐š‘๐š-3,8.

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 th 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 fact that we can translate 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.