5.191. lex_different
| DESCRIPTION | LINKS | GRAPH | AUTOMATON |
- Origin
Used for defining lex_alldifferent.
- Constraint
lex_different(VECTOR1,VECTOR2)
- Argument(s)
-
VECTOR1 collection(var−dvar) VECTOR2 collection(var−dvar) - Restriction(s)
-
required(VECTOR1,var) required(VECTOR2,var) |VECTOR1|>0 |VECTOR1|=|VECTOR2| - Purpose
Vectors VECTOR1 and VECTOR2 differ in at least one component.
- Example
-
(
)〈5,2,7,1〉, 〈5,3,7,1〉 The lex_different constraint holds since VECTOR1= 〈5,2,7,1〉 and VECTOR2= 〈5,3,7,1〉 differ in their second component.
- Reformulation
The lex_different(〈var−U1,var−U2,...,var−U|VECTOR1|〉,〈var−V1,var−V2,...,var−V|VECTOR2|〉) constraint can be expressed in term of the following disjunction of disequality constraints U1≠V1∨U2≠V2∨...∨U|VECTOR1|≠V|VECTOR2|.
- Used in
- See also
- Key words
characteristic of a constraint: vector, disequality, automaton, automaton without counters.
constraint network structure: Berge-acyclic constraint network.
- Arc input(s)
VECTOR1 VECTOR2
- Arc generator
-
PRODUCT(=)↦collection(vector1,vector2) - Arc arity
-
2 - Arc constraint(s)
-
vector1.var≠vector2.var - Graph property(ies)
-
NARC≥1
- Graph model
Parts (A) and (B) of Figure 5.191.1 respectively show the initial and final graph associated with the Example slot. Since we use the NARC graph property, the unique arc of the final graph is stressed in bold. It corresponds to a component where the two vectors differ.
Figure 5.191.1. Initial and final graph of the lex_different constraint
(a) (b)
- Automaton
Figure 5.191.2 depicts the automaton associated with the lex_different constraint. Let VAR1i and VAR2i respectively be the var attributes of the ith items of the VECTOR1 and the VECTOR2 collections. To each pair (VAR1i,VAR2i) corresponds a 0-1 signature variable Si as well as the following signature constraint: VAR1i=VAR2i⇔Si.
Figure 5.191.2. Automaton of the lex_different constraint
Figure 5.191.3. Hypergraph of the reformulation corresponding to the automaton of the lex_different constraint
