3.7.66. Core
Denotes that a global constraint is an important constraint. In fact many constraints can been seen as variations or extensions around one of the following notions:
The notion of all different forces a set of domain variables to be assigned distinct values. Given a set of domain variables , the imposes such a condition. For instance, the ground instance is satisfied, while is not, since value 1 is assigned twice.
The notion of functional dependency states that a domain variable depends directly of another domain variable. A functional dependency can either be defined in intention or in extension.
On the one hand, functional dependencies defined by intension are usually associated with numerical constraints such as, for instance, which forces the condition . They can also be associated with global constraints that mention a characteristic that is computed from one or several collections of variables. This is for instance the case for the constraint which forces to be equal to the number of distinct values assigned to .
On the other hand, functional dependencies defined by extension are more general since they allow representing any kind of functional dependency. The constraint allows expressing that a variable is determined by a variable via a table of integers , i.e., . For instance, the ground instance is satisfied since 8 is equal to the second entry of the table . Typical usages of the constraint are for instance:
Figure 3.7.19. Three counting based generalisations of the constraint: the , the and the (i.e.,Β ) constraints; the same example is reinterpreted with respect to the three generalisations
Both, the and the constraints, are the most commonly used global constraints. Many core global constraints can be seen as an extension of the constraint along one of the two following lines:
In the first line we replace the fact that each value should not be used more than once by some more involved counting constraints like:
Counting the total number of actually used distinct values like the constraint which forces to be be equal to the number of distinct values assigned to . When is set to the total number of variables, i.e.Β , and are equivalent.
Counting the number of cycles of a permutation, i.e.Β we assume that the values assigned to variables belong to interval , like the constraint. When (1)Β is unconstrained, i.e.Β it can take any value in , and when (2)Β all variables belong to , and are equivalent.
Counting the number of occurrences of each assigned value like the constraint, which forces each value to be assigned to exactly variables of . When (1)Β all the occurrence variables are 0-1 variables, and when (2)Β all variables can only be assigned values in , and are equivalent. When in addition (3)Β and for all we have a bijection between variables and values.
In the second line we generalise the disequality between two variables in some way like:
We replace the disequality between two variables by a non-overlapping condition between two tasks where a task is defined by its origin and its duration . The disequality between two variables is changed to a disjunction stating that a task ends before the start of another task or vice versa. This leads to the constraint.
We replace the disequality between two variables by a non-overlapping condition between two orthotopes where each orthotope is defined by the coordinates of its origin and by its sizes. Two orthotopes do not overlap if there exists at least one dimension where their projections do not overlap, i.e.Β the disequality between two variables is changed to a disjunction with a number of alternatives that is equal to two times the number of dimensions. This leads to the constraint.
We replace