Global Constraint Catalog: Clex

5.227. lex_different

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

Used for defining $𝚕𝚎𝚡_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ .

Constraint

$𝚕𝚎𝚡_𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝 (𝚅𝙴𝙲𝚃𝙾𝚁 1, 𝚅𝙴𝙲𝚃𝙾𝚁 2)$

Synonyms

$𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ , $𝚍𝚒𝚏𝚏$ .

Arguments

$𝚅𝙴𝙲𝚃𝙾𝚁 1$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$
$𝚅𝙴𝙲𝚃𝙾𝚁 2$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$

Restrictions

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙴𝙲𝚃𝙾𝚁 1, 𝚟𝚊𝚛)

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙴𝙲𝚃𝙾𝚁 2, 𝚟𝚊𝚛)

| 𝚅𝙴𝙲𝚃𝙾𝚁 1 | > 0

| 𝚅𝙴𝙲𝚃𝙾𝚁 1 | = | 𝚅𝙴𝙲𝚃𝙾𝚁 2 |

Purpose

Vectors $𝚅𝙴𝙲𝚃𝙾𝚁 1$ and $𝚅𝙴𝙲𝚃𝙾𝚁 2$ differ in at least one component.

Example

(〈5, 2, 7, 1〉, 〈5, 3, 7, 1〉)

The $𝚕𝚎𝚡_𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ constraint holds since $𝚅𝙴𝙲𝚃𝙾𝚁 1 =$ $〈 5, 2, 7, 1 〉$ and $𝚅𝙴𝙲𝚃𝙾𝚁 2 =$ $〈 5, 3, 7, 1 〉$ differ in their second component.

Typical

| 𝚅𝙴𝙲𝚃𝙾𝚁 1 | > 1

𝚛𝚊𝚗𝚐𝚎

(𝚅𝙴𝙲𝚃𝙾𝚁 1 . 𝚟𝚊𝚛) > 1

𝚛𝚊𝚗𝚐𝚎

(𝚅𝙴𝙲𝚃𝙾𝚁 2 . 𝚟𝚊𝚛) > 1

Symmetries

Arguments are permutable w.r.t. permutation $(𝚅𝙴𝙲𝚃𝙾𝚁 1, 𝚅𝙴𝙲𝚃𝙾𝚁 2)$ .
Items of $𝚅𝙴𝙲𝚃𝙾𝚁 1$ and $𝚅𝙴𝙲𝚃𝙾𝚁 2$ are permutable (same permutation used).

Arg. properties

Extensible wrt. $𝚅𝙴𝙲𝚃𝙾𝚁 1$ and $𝚅𝙴𝙲𝚃𝙾𝚁 2$ (add items at same position).

Reformulation

The $𝚕𝚎𝚡_𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ $(〈 𝚟𝚊𝚛 - U_{1}, 𝚟𝚊𝚛 - U_{2}, \dots, 𝚟𝚊𝚛 - U_{| 𝚅𝙴𝙲𝚃𝙾𝚁 1 |} 〉, 〈 𝚟𝚊𝚛 - V_{1}, 𝚟𝚊𝚛 - V_{2}, \dots, 𝚟𝚊𝚛 - V_{| 𝚅𝙴𝙲𝚃𝙾𝚁 2 |} 〉)$ constraint can be expressed in term of the following disjunction of disequality constraints $U_{1} \neq V_{1} \lor U_{2} \neq V_{2} \lor \dots \lor U_{| 𝚅𝙴𝙲𝚃𝙾𝚁 1 |} \neq V_{| 𝚅𝙴𝙲𝚃𝙾𝚁 2 |}$ .

Used in

$𝚕𝚎𝚡_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ , $𝚜𝚘𝚛𝚝_𝚙𝚎𝚛𝚖𝚞𝚝𝚊𝚝𝚒𝚘𝚗$ .

implied by: $𝚍𝚒𝚜𝚓𝚘𝚒𝚗𝚝$ , $𝚒𝚗𝚌𝚘𝚖𝚙𝚊𝚛𝚊𝚋𝚕𝚎$ , $𝚕𝚎𝚡_𝚐𝚛𝚎𝚊𝚝𝚎𝚛$ , $𝚕𝚎𝚡_𝚕𝚎𝚜𝚜$ .

negation: $𝚕𝚎𝚡_𝚎𝚚𝚞𝚊𝚕$ .

system of constraints: $𝚕𝚎𝚡_𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ .

Keywords

characteristic of a constraint: vector, disequality, automaton, automaton without counters, reified automaton constraint.

constraint network structure: Berge-acyclic constraint network.

filtering: arc-consistency.

Arc input(s)

$𝚅𝙴𝙲𝚃𝙾𝚁 1$ $𝚅𝙴𝙲𝚃𝙾𝚁 2$

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

(=) \mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚎𝚌𝚝𝚘𝚛 1, 𝚟𝚎𝚌𝚝𝚘𝚛 2)

Arc arity

Arc constraint(s)

𝚟𝚎𝚌𝚝𝚘𝚛 1 . 𝚟𝚊𝚛 \neq 𝚟𝚎𝚌𝚝𝚘𝚛 2 . 𝚟𝚊𝚛

Graph property(ies)

𝐍𝐀𝐑𝐂

\geq 1

Graph model

Parts (A) and (B) of Figure 5.227.1 respectively show the initial and final graph associated with the Example slot. Since we use the $𝐍𝐀𝐑𝐂$ 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.227.1. Initial and final graph of the $𝚕𝚎𝚡_𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ constraint


(a)	(b)

Automaton: Figure 5.227.2 depicts the automaton associated with the $𝚕𝚎𝚡_𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ constraint. Let $𝚅𝙰𝚁 1_{i}$ and $𝚅𝙰𝚁 2_{i}$ respectively be the $𝚟𝚊𝚛$ attributes of the $i^{t h}$ items of the $𝚅𝙴𝙲𝚃𝙾𝚁 1$ and the $𝚅𝙴𝙲𝚃𝙾𝚁 2$ collections. To each pair $(𝚅𝙰𝚁 1_{i}, 𝚅𝙰𝚁 2_{i})$ corresponds a 0-1 signature variable $S_{i}$ as well as the following signature constraint: $𝚅𝙰𝚁 1_{i} = 𝚅𝙰𝚁 2_{i} \Leftrightarrow S_{i}$ .

Figure 5.227.2. Automaton of the $𝚕𝚎𝚡_𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ constraint

Figure 5.227.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚕𝚎𝚡_𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.227. lex_different

Figure 5.227.1. Initial and final graph of the $𝚕𝚎𝚡_𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ constraint

Figure 5.227.2. Automaton of the $𝚕𝚎𝚡_𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ constraint

Figure 5.227.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚕𝚎𝚡_𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.227. lex_different

Figure 5.227.1. Initial and final graph of the 𝚕𝚎𝚡_𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝 constraint

Figure 5.227.2. Automaton of the 𝚕𝚎𝚡_𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝 constraint

Figure 5.227.3. Hypergraph of the reformulation corresponding to the automaton of the 𝚕𝚎𝚡_𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝 constraint

Figure 5.227.1. Initial and final graph of the $𝚕𝚎𝚡_𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ constraint

Figure 5.227.2. Automaton of the $𝚕𝚎𝚡_𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ constraint

Figure 5.227.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚕𝚎𝚡_𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ constraint