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 we can swap both arguments and still get a solution (i.e., ).
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 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., ).
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 we can interchange attributes and and still get a solution (i.e., ).
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 , 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 . 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 constraint which, given two domain variables , and an integer value , forces the condition . Within the electronic catalogue this is represented by the following meta-data, , to which corresponds the following textual form:
ย ย ย ย arguments are permutable w.r.t.ย permutation .
Note that, even though arguments and do not have the same type (i.e., is a domain variable, while is an integer value), both arguments can be exchanged since we consider the ground case. For instance, since is satisfied, is also satisfied.
EXAMPLEย 2: As a second example where we can swap several arguments, consider the constraint which, given two domain variables , and two collections of domain variables , , forces the following two conditions:
is the number of variables of assigned a value in .
is the number of variables of assigned a value in .
Within the electronic catalogue this is represented by the following meta-data, , to which corresponds the following textual form:
ย ย ย ย arguments are permutable w.r.t. permutation
ย ย ย ย .
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:
An argument of the global constraint that corresponds to a of items.
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 items , a permutation of , not necessarily the same, is applied on the items of a subset of the set of collections .
represents a set of permutations. It can take one of the following values:
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.
stands for the set that only contains the permutation that maps the sequence to .
stands for the set that only contains the permutation that maps the sequence to .
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 is satisfied, all permutations of (i.e., , , , , , ) 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 is satisfied, it is also satisfied for all permutations of the elements of its second set , 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:
If contains a single element then this element has the form . This is done to allow to designate more than a single collection.
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:
stands for all possible permutations.
stands for the set that only contains the permutation that maps the sequence to .
stands for the set that only contains the permutation that maps the sequence to .
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 successive maximum groups of consecutive ones of have sizes , , , . 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 is a solution, 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 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 of type can be exchanged with an attribute 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 is a solution, 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 and 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 is a solution, 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 or , where:
is an argument of the global constraint of type domain variable, integer, or collection of domain variables or integers.
is a path to an integer attribute or to a collection of integers attribute of the global constraint. , , ..., 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 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 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 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 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, and 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 .
, where (respectively ) is an argument of type collection and (respectively ) is an attribute of (respectively ) of type integer or domain variable, denotes the set of all elements of that are assigned to but not to .
, denotes the set .
, , denotes the set of all integers such that the comparison holds.
, , denotes the set of all integers located in interval .
, , denotes the set of all integers not located in interval .
, , denotes all integer values in that have as remainder when divided by .remainder.
Given set of values generators , , , , a compound set of values generator is defined by:
denotes all values that are in at least one of the sets , , , .
denotes all values of that are not in any set , , , .
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 .
, , denotes a partition containing intervals of the form , .
, , denotes a partition such that each class of is made up from all integers in that have the same remainder when divided by .remainder.
, where 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 . Classes are ordered with respect to their occurrences in .
When defines a partition of tuples, where each tuple consists of integers, can only be set to . In this context denotes a partition where, to each element of corresponds a specific class of containing just that element.
is one of the symbols , , , , , , or . It specifies a set of pairs of elements of the partition such that, when is different from ,When is equal to we just consider all possible pairs. the condition holds for all . The aim of the parameter is to allow to specify which partitions of the source value and the target value should belong to. In fact there should exist a pair , , such that and .
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,
a ground instance of a global constraint ,
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 ,
the sets of values that are assigned to in the ground instance of ,We may have more than one set when the path does not start from a top level collection.
a partition of integer values derived from ,
a set of pairs of elements of the partition such that the condition holds for all ,
a option.
Given one of the sets of values , , a source value can be permuted with a target value if and only if the following conditions are all satisfied:
(source and target values should be distinct),
(source value, i.e., value that is replaced, should be part of the solution),
(source and target values should be located in the appropriate partition classes),
(if then the target value should also be part of the solution).
If is equal to we replace each occurrence of by , and conversely each occurrence of by . Otherwise we replace at least one occurrence of by .
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, , 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 is a solution, we can replace value 9 by a not yet assigned value, 0 for instance, and get another valid solution .
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 ย .
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, , 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 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 . We can also swap all occurrences of value 1 and value 3, and get another valid solution .
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 ย .
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 forces for each pair of distinct variables of the collection that . Note that we can exchange two occurrences of distinct values of , but we cannot replace an existing value by a new value (since the new value may be too close from another existing value , i.e., ). 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 is a solution, we can swap values 5 and 9, and get another valid solution .
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 ย .
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 by a new value (since the new value 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 is a solution, we can swap values 2 and 6, and get another valid solution .
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 ย .
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 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 .
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 corresponding to all values in , and a second set corresponding to all values not in .
indicates that the exchange of values takes place within the same set, i.e., within or within .
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, , 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 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 . We can also replace the second occurrence of value 2 with value 4 and get another valid solution .
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 containing only value , and a second set corresponding to all values different from .
indicates that the the source and target values should respectively belong to sets and where :
If the source value is different from (i.e., the source value belongs to ), then the target value can indifferently be equal or not equal to (i.e., the target value belongs to or ).
If the source value is equal to (i.e., the source value belongs to ), then the target value is equal to (i.e., the target value also belongs to ). 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, , 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 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 . But, within , we can also replace value 2 with any other value, e.g.ย value 4 and get another valid solution .
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 containing only value , and a second set corresponding to all values different from .
indicates that the the source and target values should respectively belong to sets and where :
If the source value is different from (i.e., the source value belongs to ), then the target value is also different from (i.e., the target value belongs to ). This supports the fact that we do not want to increase the number of occurrences of value .
If the source value is equal to (i.e., the source value belongs to ), then there is no restriction on the target value (i.e., the target value belongs to or to ). But the set 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 constraint, which forces the two following conditions:
is the number of variables of the collection taking a value in .
is the number of variables of the collection taking a value in .
Note that we can exchange all occurrences of two distinct values of or , or replace all occurrences of an assigned value of or by a new value, i.e., a value that is not yet assigned to any variable of and . 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 in or can be swapped; all occurrences of a value in or can be renamed to any unused value.
For instance, since 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 .
The five parameters of have the following meaning:
indicates that the modification takes place within the values assigned to the attribute of the and collections.
defines the partition of values ย .
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 or .
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 constraint, which forces to be less than or equal to . Note that can be decreased to any value, and that can be increased up to . Similarly, can be increased to any value, and can be decreased down to . Within the electronic catalogue this is respectively represented by the following meta-data, and , to which corresponds the following textual form:
ย ย ย ย can be replaced by any value ;
ย ย ย ย can be replaced by any value .
For instance, since 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 . But, within , 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 .
The five parameters of have the following meaning:
indicates that the modification takes place within the value assigned to the argument of the constraint .
defines the partition of values (i.e., we only consider values that are less than or equal to ).
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 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, , 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 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 . From the solution , we can also swap all occurrences of two values, e.g. values 1 and 2, and get another valid solution .
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 ย .
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, , to which corresponds the following textual form:
ย ย ย ย An occurrence of a value of can be replaced by any value of .
For instance, since 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 .
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 a single set.
defines the partition of values ย .
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, , 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 is a solution, we can replace all the occurrences of the tuple of values by any unused tuple of values, e.g.ย the tuple of values , and get another valid solution .
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 , or , or , where:
is an argument of the global constraint of type domain variable or integer.
is an argument of the global constraint that corresponds to a collection, and is an attribute of of type domain variable or integer.
is an argument of the global constraint that corresponds to a collection, and is an attribute of of type collection, and is an attribute of 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 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 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 corresponds to the fact that we want to increment attribute of all items corresponding to .
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 of distinct variables of the collection that . 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 is a solution, we can add the constant 6 to all items of the collection , and get another valid solution .
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
is a solution, we can add the constant 2 to all and attributes, and get another valid solution
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 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 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.