Global Constraint Catalog: Clex

5.228. lex_equal

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

Initially introduced for defining $𝚗𝚟𝚎𝚌𝚝𝚘𝚛$

Constraint

$𝚕𝚎𝚡_𝚎𝚚𝚞𝚊𝚕 (𝚅𝙴𝙲𝚃𝙾𝚁 1, 𝚅𝙴𝙲𝚃𝙾𝚁 2)$

Synonyms

$𝚎𝚚𝚞𝚊𝚕$ , $𝚎𝚚$ .

Arguments

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

Restrictions

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

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

Purpose

$𝚅𝙴𝙲𝚃𝙾𝚁 1$ is equal to $𝚅𝙴𝙲𝚃𝙾𝚁 2$ . Given two vectors, $\vec{X}$ and $\vec{Y}$ of $n$ components, $〈 X_{0}, \dots, X_{n - 1} 〉$ and $〈 Y_{0}, \dots, Y_{n - 1} 〉$ , $\vec{X}$ is equal to $\vec{Y}$ if and only if $n = 0$ or $X_{0} = Y_{0} \land X_{1} = Y_{1} \land \dots \land X_{n - 1} = Y_{n - 1}$ .

Example

(〈1, 9, 1, 5〉, 〈1, 9, 1, 5〉)

The $𝚕𝚎𝚡_𝚎𝚚𝚞𝚊𝚕$ constraint holds since (1) the first component of the first vector is equal to the first component of the second vector, (2) the second component of the first vector is equal to the second component of the second vector, (3) the third component of the first vector is equal to the third component of the second vector and (4) the fourth component of the first vector is equal to the fourth component of the second vector.

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

Contractible wrt. $𝚅𝙴𝙲𝚃𝙾𝚁 1$ and $𝚅𝙴𝙲𝚃𝙾𝚁 2$ (remove items from same position).

Used in

$𝚊𝚝𝚕𝚎𝚊𝚜𝚝_𝚗𝚟𝚎𝚌𝚝𝚘𝚛$ , $𝚊𝚝𝚖𝚘𝚜𝚝_𝚗𝚟𝚎𝚌𝚝𝚘𝚛$ , $𝚗𝚟𝚎𝚌𝚝𝚘𝚛$ , $𝚗𝚟𝚎𝚌𝚝𝚘𝚛𝚜$ .

implied by: $𝚟𝚎𝚌_𝚎𝚚_𝚝𝚞𝚙𝚕𝚎$ .

implies: $𝚕𝚎𝚡_𝚐𝚛𝚎𝚊𝚝𝚎𝚛𝚎𝚚$ , $𝚕𝚎𝚡_𝚕𝚎𝚜𝚜𝚎𝚚$ , $𝚜𝚊𝚖𝚎$ .

negation: $𝚕𝚎𝚡_𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ .

specialisation: $𝚟𝚎𝚌_𝚎𝚚_𝚝𝚞𝚙𝚕𝚎$ ( $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ replaced by $𝚒𝚗𝚝𝚎𝚐𝚎𝚛$ in second argument).

Keywords

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

constraint network structure: Berge-acyclic constraint network.

filtering: arc-consistency.

final graph structure: acyclic, bipartite, no loop.

Arc input(s)

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

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

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

Arc arity

Arc constraint(s)

𝚟𝚎𝚌𝚝𝚘𝚛 1 . 𝚟𝚊𝚛 = 𝚟𝚎𝚌𝚝𝚘𝚛 2 . 𝚟𝚊𝚛

Graph property(ies)

𝐍𝐀𝐑𝐂

= | 𝚅𝙴𝙲𝚃𝙾𝚁 1 |

Graph class

•

𝙰𝙲𝚈𝙲𝙻𝙸𝙲

•

𝙱𝙸𝙿𝙰𝚁𝚃𝙸𝚃𝙴

•

𝙽𝙾_𝙻𝙾𝙾𝙿

Graph model

Parts (A) and (B) of Figure 5.228.1 respectively show the initial and final graphs associated with the Example slot. Since we use the $𝐍𝐀𝐑𝐂$ graph property, the arcs of the final graph are stressed in bold.

Figure 5.228.1. Initial and final graph of the $𝚕𝚎𝚡_𝚎𝚚𝚞𝚊𝚕$ constraint


(a)	(b)

Automaton: Figure 5.228.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 signature variable $S_{i}$ as well as the following signature constraint: $(𝚅𝙰𝚁 1_{i} \neq 𝚅𝙰𝚁 2_{i} \Leftrightarrow S_{i} = 0) \land (𝚅𝙰𝚁 1_{i} = 𝚅𝙰𝚁 2_{i} \Leftrightarrow S_{i} = 1)$ .

Figure 5.228.2. Automaton of the $𝚕𝚎𝚡_𝚎𝚚𝚞𝚊𝚕$ constraint

Figure 5.228.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚕𝚎𝚡_𝚎𝚚𝚞𝚊𝚕$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.228. lex_equal

Figure 5.228.1. Initial and final graph of the $𝚕𝚎𝚡_𝚎𝚚𝚞𝚊𝚕$ constraint

Figure 5.228.2. Automaton of the $𝚕𝚎𝚡_𝚎𝚚𝚞𝚊𝚕$ constraint

Figure 5.228.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚕𝚎𝚡_𝚎𝚚𝚞𝚊𝚕$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.228. lex_equal

Figure 5.228.1. Initial and final graph of the 𝚕𝚎𝚡_𝚎𝚚𝚞𝚊𝚕 constraint

Figure 5.228.2. Automaton of the 𝚕𝚎𝚡_𝚎𝚚𝚞𝚊𝚕 constraint

Figure 5.228.3. Hypergraph of the reformulation corresponding to the automaton of the 𝚕𝚎𝚡_𝚎𝚚𝚞𝚊𝚕 constraint

Figure 5.228.1. Initial and final graph of the $𝚕𝚎𝚡_𝚎𝚚𝚞𝚊𝚕$ constraint

Figure 5.228.2. Automaton of the $𝚕𝚎𝚡_𝚎𝚚𝚞𝚊𝚕$ constraint

Figure 5.228.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚕𝚎𝚡_𝚎𝚚𝚞𝚊𝚕$ constraint