5.338. same_interval
DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Arguments
- Restrictions
- Purpose
Let (respectively ) denote the number of variables of the collection (respectively ) that take a value in the interval . For all integer we have .
- Example
-
In the example, the third argument defines the following family of intervals , where is an integer. Consequently the values of the collection are respectively located within intervals , , , , , . Therefore intervals and are respectively used 3 and 3 times. Similarly, the values of the collection are respectively located within intervals , , , , , . As before intervals and are respectively used 3 and 3 times. Consequently the constraint holds. FigureΒ 5.338.1 illustrates this correspondence.
Figure 5.338.1. Illustration of the correspondence between the items of the and of the collections of the Example slot
- Typical
- Symmetries
Arguments are permutable w.r.t. permutation .
Items of are permutable.
Items of are permutable.
An occurrence of a value of that belongs to the -th interval, of size , can be replaced by any other value of the same interval.
- Arg. properties
Aggregate: , , .
- Algorithm
- Used in
- See also
implies: .
soft variant: Β (variable-based violation measure).
specialisation: Β ( replaced by ).
- Keywords
characteristic of a constraint: sort based reformulation.
combinatorial object: permutation.
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.338.2 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. The constraint holds since:
Each connected component of the final graph has the same number of sources and of sinks.
The number of sources of the final graph is equal to .
The number of sinks of the final graph is equal to .
Figure 5.338.2. Initial and final graph of the constraint
(a) (b) - Signature
Since the initial graph contains only sources and sinks, and since isolated vertices are eliminated from the final graph, we make the following observations:
Sources of the initial graph cannot become sinks of the final graph,
Sinks of the initial graph cannot become sources of the final graph.
From the previous observations and since we use the arc generator on the collections and , we have that the maximum number of sources and sinks of the final graph is respectively equal to and . Therefore we can rewrite to and simplify to . In a similar way, we can rewrite to and simplify to .