5.415. used_by_partition
DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Type
- Arguments
- Restrictions
- Purpose
For each integer in , let (respectively ) denote the number of variables of (respectively ) that take their value in the partition of the collection . For all in we have .
- Example
-
The different values of the collection are respectively associated with the partitions , , , and . Therefore partitions and are respectively used 2 and 2 times.
Similarly, the different values of the collection (except value 9, which does not occur in any partition) are respectively associated with the partitions , , , , and . Therefore partitions and are respectively used 3 and 2 times.
Consequently, the constraint holds since, for each partition associated with the collection , its number of occurrences within is greater than or equal to its number of occurrences within :
Partition occurs 3 times within and 2 times within .
Partition occurs 2 times within and 2 times within .
- Typical
- Symmetries
Items of are permutable.
Items of are permutable.
Items of are permutable.
Items of are permutable.
An occurrence of a value of can be replaced by any other value that also belongs to the same partition of .
An occurrence of a value of can be replaced by any other value that also belongs to the same partition of .
- Arg. properties
Contractible wrt. .
Extensible wrt. .
Aggregate: , , .
- Used in
- See also
-
soft variant: Β (variable-based violation measure).
specialisation: Β ( replaced by ).
- Keywords
characteristic of a constraint: partition, sort based reformulation.
constraint arguments: constraint between two collections of variables.
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Graph model
PartsΒ (A) andΒ (B) of FigureΒ 5.415.1 respectively show the initial and final graph associated with the Example slot. Since we use the and graph properties, the source and sink vertices of the final graph are stressed with a double circle. Since there is a constraint on each connected component of the final graph we also show the different connected components. Each of them corresponds to an equivalence class according to the arc constraint. Note that the vertex corresponding to the variable that takes value 9 was removed from the final graph since there is no arc for which the associated equivalence constraint holds. The constraint holds since:
For each connected component of the final graph the number of sources is greater than or equal to the number of sinks.
The number of sinks of the final graph is equal to .
Figure 5.415.1. Initial and final graph of the constraint
(a) (b) - Signature
Since the initial graph contains only sources and sinks, and since sources of the initial graph cannot become sinks of the final graph, we have that the maximum number of sinks of the final graph is equal to . Therefore we can rewrite to and simplify to .