5.13. alldifferent_between_sets
| DESCRIPTION | LINKS | GRAPH |
- Origin
ILOG
- Constraint
- Synonyms
, , , , , .
- Argument
- Restriction
- Purpose
Enforce all sets of the collection to be distinct.
- Example
-
The constraint holds since all the sets , , and are distinct.
- Typical
- Symmetry
Items of are permutable.
- Arg. properties
Contractible wrt. .
- Usage
This constraint was available in some configuration library offered by Ilog.
- Algorithm
A filtering algorithm for the is proposed by C.-G.Β Quimper and T.Β Walsh inΒ [QuimperWalsh05] and a longer version is available inΒ [QuimperWalshReport05] and inΒ [QuimperWalsh06].
- See also
common keyword: Β (constraint involving set variables).
specialisation: Β ( replaced by ).
- Keywords
characteristic of a constraint: all different, disequality.
constraint arguments: constraint involving set variables.
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
- Graph property(ies)
-
- Graph class
-
- Graph model
We generate a clique with binary set equalities constraints between each pair of vertices (including a vertex and itself) and state that the size of the largest strongly connected component should not exceed 1.
PartsΒ (A) andΒ (B) of FigureΒ 5.13.1 respectively show the initial and final graph associated with the Example slot. Since we use the graph property we show one of the largest strongly connected components of the final graph. The holds since all the strongly connected components have at most one vertex.
Figure 5.13.1. Initial and final graph of the constraint
(a) 
(b)