5.294. open_alldifferent
| DESCRIPTION | LINKS | GRAPH |
- Origin
- Constraint
- Synonyms
, , .
- Arguments
- Restrictions
- Purpose
Let be the variables of the collection for which the corresponding position belongs to the set . Positions are numbered from 1. Enforce all variables of to take distinct values.
- Example
-
The constraint holds since the last three (i.e.,Β ) values of the collection are distinct.
- Typical
- Symmetry
All occurrences of two distinct values of can be swapped; all occurrences of a value of can be renamed to any unused value.
- Arg. properties
Suffix-contractible wrt. .
- Usage
In their articleΒ [HoeveRegin06], W.-J.Β vanΒ Hoeve and J.-C.Β RΓ©gin motivate the constraint by the following scheduling problem. Consider a set of activities (where each activity has a fixed duration 1 and a start variable) that can be processed on two factory lines such that all the activities that will be processed on a given line must be pairwise distinct. This can be modelled by using one constraint for each line, involving all the start variables as well as a set variable whose final value specifies the set of activities assigned to that specific factory line.
Note that this can also be directly modelled by a single constraint. This is done by introducing an assignment variable for each activity. The initial domain of each assignment variable consists of two values that respectively correspond to the two factory lines.
- Algorithm
A slight adaptation of the flow model that handles the original constraintΒ [Regin96] is described inΒ [HoeveRegin06]. The rightmost part of FigureΒ 3.7.28 illustrates this flow model.
- See also
common keyword: , Β (all different,disequality).
generalisation: Β (control the number of occurrence of each active valueAn active value corresponds to a value occuring at a position mentionned in the set . with a counter variable), Β (control the number of occurrence of each active value with an interval).
- Keywords
characteristic of a constraint: all different, disequality.
constraint arguments: constraint involving set variables.
constraint type: open constraint, soft constraint, value constraint.
- Arc input(s)
- Arc generator
-
- Arc arity
- Arc constraint(s)
-
- Graph property(ies)
-
- Graph class
-
- Graph model
We generate a clique with an equality constraint between each pair of vertices (including a vertex and itself) and state that the size of the largest strongly connected component should not exceed one. Variables for which the corresponding position does not belong to the set are removed from the final graph by the second and third conditions of the arc-constraint.
PartsΒ (A) andΒ (B) of FigureΒ 5.294.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: a value is used at most once.
Figure 5.294.1. Initial and final graph of the constraint
(a) (b)