Global Constraint Catalog: Celement

5.142. element_matrix

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

CHIP

Constraint

$𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚖𝚊𝚝𝚛𝚒𝚡 (𝙼𝙰𝚇_𝙸, 𝙼𝙰𝚇_𝙹, 𝙸𝙽𝙳𝙴𝚇_𝙸, 𝙸𝙽𝙳𝙴𝚇_𝙹, 𝙼𝙰𝚃𝚁𝙸𝚇, 𝚅𝙰𝙻𝚄𝙴)$

Synonyms

$𝚎𝚕𝚎𝚖_𝚖𝚊𝚝𝚛𝚒𝚡$ , $𝚖𝚊𝚝𝚛𝚒𝚡$ .

Arguments

$𝙼𝙰𝚇_𝙸$	$𝚒𝚗𝚝$
$𝙼𝙰𝚇_𝙹$	$𝚒𝚗𝚝$
$𝙸𝙽𝙳𝙴𝚇_𝙸$	$𝚍𝚟𝚊𝚛$
$𝙸𝙽𝙳𝙴𝚇_𝙹$	$𝚍𝚟𝚊𝚛$
$𝙼𝙰𝚃𝚁𝙸𝚇$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚒 - 𝚒𝚗𝚝, 𝚓 - 𝚒𝚗𝚝, 𝚟 - 𝚒𝚗𝚝)$
$𝚅𝙰𝙻𝚄𝙴$	$𝚍𝚟𝚊𝚛$

Restrictions

𝙼𝙰𝚇_𝙸 \geq 1

𝙼𝙰𝚇_𝙹 \geq 1

𝙸𝙽𝙳𝙴𝚇_𝙸 \geq 1

𝙸𝙽𝙳𝙴𝚇_𝙸 \leq 𝙼𝙰𝚇_𝙸

𝙸𝙽𝙳𝙴𝚇_𝙹 \geq 1

𝙸𝙽𝙳𝙴𝚇_𝙹 \leq 𝙼𝙰𝚇_𝙹

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝙼𝙰𝚃𝚁𝙸𝚇, [𝚒, 𝚓, 𝚟])

𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚎𝚚

(𝙼𝙰𝚃𝚁𝙸𝚇, [𝚒, 𝚓])

𝙼𝙰𝚃𝚁𝙸𝚇 . 𝚒 \geq 1

𝙼𝙰𝚃𝚁𝙸𝚇 . 𝚒 \leq 𝙼𝙰𝚇_𝙸

𝙼𝙰𝚃𝚁𝙸𝚇 . 𝚓 \geq 1

𝙼𝙰𝚃𝚁𝙸𝚇 . 𝚓 \leq 𝙼𝙰𝚇_𝙹

| 𝙼𝙰𝚃𝚁𝙸𝚇 | = 𝙼𝙰𝚇_𝙸 * 𝙼𝙰𝚇_𝙹

Purpose

The $𝙼𝙰𝚃𝚁𝙸𝚇$ collection corresponds to the two-dimensional matrix $𝙼𝙰𝚃𝚁𝙸𝚇 [1 . . 𝙼𝙰𝚇_𝙸, 1 . . 𝙼𝙰𝚇_𝙹]$ . $𝚅𝙰𝙻𝚄𝙴$ is equal to the entry $𝙼𝙰𝚃𝚁𝙸𝚇 [𝙸𝙽𝙳𝙴𝚇_𝙸, 𝙸𝙽𝙳𝙴𝚇_𝙹]$ of the previous matrix.

Example

(\begin{matrix} 4, 3, 1, 3, 〈\begin{matrix} 𝚒 - 1 & 𝚓 - 1 & 𝚟 - 4, \\ 𝚒 - 1 & 𝚓 - 2 & 𝚟 - 1, \\ 𝚒 - 1 & 𝚓 - 3 & 𝚟 - 7, \\ 𝚒 - 2 & 𝚓 - 1 & 𝚟 - 1, \\ 𝚒 - 2 & 𝚓 - 2 & 𝚟 - 0, \\ 𝚒 - 2 & 𝚓 - 3 & 𝚟 - 8, \\ 𝚒 - 3 & 𝚓 - 1 & 𝚟 - 3, \\ 𝚒 - 3 & 𝚓 - 2 & 𝚟 - 2, \\ 𝚒 - 3 & 𝚓 - 3 & 𝚟 - 1, \\ 𝚒 - 4 & 𝚓 - 1 & 𝚟 - 0, \\ 𝚒 - 4 & 𝚓 - 2 & 𝚟 - 0, \\ 𝚒 - 4 & 𝚓 - 3 & 𝚟 - 6 \end{matrix}〉, 7 \end{matrix})

The $𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚖𝚊𝚝𝚛𝚒𝚡$ constraint holds since its last argument $𝚅𝙰𝙻𝚄𝙴 = 7$ is equal to the $𝚟$ attribute of the $k^{t h}$ item of the $𝙼𝙰𝚃𝚁𝙸𝚇$ collection such that $𝙼𝙰𝚃𝚁𝙸𝚇 [k] . i = 𝙸𝙽𝙳𝙴𝚇_𝙸 = 1$ and $𝙼𝙰𝚃𝚁𝙸𝚇 [k] . j = 𝙸𝙽𝙳𝙴𝚇_𝙹 = 3$ .

Typical

𝙼𝙰𝚇_𝙸 > 1

𝙼𝙰𝚇_𝙹 > 1

| 𝙼𝙰𝚃𝚁𝙸𝚇 | > 3

𝚖𝚊𝚡𝚟𝚊𝚕

(𝙼𝙰𝚃𝚁𝙸𝚇 . 𝚒) > 1

𝚖𝚊𝚡𝚟𝚊𝚕

(𝙼𝙰𝚃𝚁𝙸𝚇 . 𝚓) > 1

𝚛𝚊𝚗𝚐𝚎

(𝙼𝙰𝚃𝚁𝙸𝚇 . 𝚟) > 1

Symmetry

All occurrences of two distinct values in $𝙼𝙰𝚃𝚁𝙸𝚇 . 𝚟$ or $𝚅𝙰𝙻𝚄𝙴$ can be swapped; all occurrences of a value in $𝙼𝙰𝚃𝚁𝙸𝚇 . 𝚟$ or $𝚅𝙰𝙻𝚄𝙴$ can be renamed to any unused value.

Reformulation

The $𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚖𝚊𝚝𝚛𝚒𝚡$ $(𝙼𝙰𝚇_𝙸, 𝙼𝙰𝚇_𝙹, 𝙸𝙽𝙳𝙴𝚇_𝙸, 𝙸𝙽𝙳𝙴𝚇_𝙹, 𝙼𝙰𝚃𝚁𝙸𝚇, 𝚅𝙰𝙻𝚄𝙴)$ constraint can be expressed in term of $𝙼𝙰𝚇_𝙸$ $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ $(𝙸𝙽𝙳𝙴𝚇_𝙹, {𝙻𝙸𝙽𝙴}_{i}, {𝚅𝙰𝚁}_{i})$ $(i \in [1, 𝙼𝙰𝚇_𝙸])$ , where ${𝙻𝙸𝙽𝙴}_{i}$ corresponds to the $i$ -th line of the matrix $𝙼𝙰𝚃𝚁𝙸𝚇$ and of one $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ $(𝙸𝙽𝙳𝙴𝚇_𝙸, 〈 {𝚅𝙰𝚁}_{1}, {𝚅𝙰𝚁}_{2}, \dots, {𝚅𝙰𝚁}_{𝙼𝙰𝚇_𝙸} 〉, 𝚅𝙰𝙻𝚄𝙴)$ constraint.

If we consider the Example slot we get the following $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ constraints:

$𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ $(3, 〈 4, 1, 7 〉, 7)$ ,
$𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ $(3, 〈 1, 0, 8 〉, 8)$ ,
$𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ $(3, 〈 3, 2, 1 〉, 1)$ ,
$𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ $(3, 〈 0, 0, 6 〉, 6)$ ,
$𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ $(1, 〈 7, 8, 1, 6 〉, 7)$ .

Systems

nth in Choco, element in Gecode.

Keywords

characteristic of a constraint: automaton, automaton without counters, reified automaton constraint, derived collection.

constraint arguments: ternary constraint.

constraint network structure: centered cyclic(3) constraint network(1).

constraint type: data constraint.

filtering: arc-consistency.

modelling: array constraint, matrix.

Derived Collection

𝚌𝚘𝚕 (\begin{matrix} 𝙸𝚃𝙴𝙼 - 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚒𝚗𝚍𝚎𝚡_𝚒 - 𝚍𝚟𝚊𝚛, 𝚒𝚗𝚍𝚎𝚡_𝚓 - 𝚍𝚟𝚊𝚛, 𝚟𝚊𝚕𝚞𝚎 - 𝚍𝚟𝚊𝚛), \\ 𝚒𝚝𝚎𝚖 (𝚒𝚗𝚍𝚎𝚡_𝚒 - 𝙸𝙽𝙳𝙴𝚇_𝙸, 𝚒𝚗𝚍𝚎𝚡_𝚓 - 𝙸𝙽𝙳𝙴𝚇_𝙹, 𝚟𝚊𝚕𝚞𝚎 - 𝚅𝙰𝙻𝚄𝙴)] \end{matrix})

Arc input(s)

$𝙸𝚃𝙴𝙼$ $𝙼𝙰𝚃𝚁𝙸𝚇$

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚒𝚝𝚎𝚖, 𝚖𝚊𝚝𝚛𝚒𝚡)

Arc arity

Arc constraint(s)

• 𝚒𝚝𝚎𝚖 . 𝚒𝚗𝚍𝚎𝚡_𝚒 = 𝚖𝚊𝚝𝚛𝚒𝚡 . 𝚒

• 𝚒𝚝𝚎𝚖 . 𝚒𝚗𝚍𝚎𝚡_𝚓 = 𝚖𝚊𝚝𝚛𝚒𝚡 . 𝚓

• 𝚒𝚝𝚎𝚖 . 𝚟𝚊𝚕𝚞𝚎 = 𝚖𝚊𝚝𝚛𝚒𝚡 . 𝚟

Graph property(ies)

𝐍𝐀𝐑𝐂

= 1

Graph model

Similar to the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝$ constraint except that the arc constraint is updated according to the fact that we have a two-dimensional matrix.

Parts (A) and (B) of Figure 5.142.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.

Figure 5.142.1. Initial and final graph of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚖𝚊𝚝𝚛𝚒𝚡$ constraint

(a)

(b)

Signature

Because of the first condition of the arc constraint the final graph cannot have more than one arc. Therefore we can rewrite $𝐍𝐀𝐑𝐂 = 1$ to $𝐍𝐀𝐑𝐂 \geq 1$ and simplify $\underset{̲}{\bar{𝐍𝐀𝐑𝐂}}$ to $\bar{𝐍𝐀𝐑𝐂}$ .

Automaton: Figure 5.142.2 depicts the automaton associated with the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚖𝚊𝚝𝚛𝚒𝚡$ constraint. Let $𝙸_{k}$ , $𝙹_{k}$ and $𝚅_{k}$ respectively be the $𝚒$ , the $𝚓$ and the $𝚟$ $k^{t h}$ attributes of the $𝙼𝙰𝚃𝚁𝙸𝚇$ collection. To each sextuple $(𝙸𝙽𝙳𝙴𝚇_𝙸, 𝙸𝙽𝙳𝙴𝚇_𝙹, 𝚅𝙰𝙻𝚄𝙴, 𝙸_{k}, 𝙹_{k}, 𝚅_{k})$ corresponds a 0-1 signature variable $S_{k}$ as well as the following signature constraint: $((𝙸𝙽𝙳𝙴𝚇_𝙸 = 𝙸_{k}) \land (𝙸𝙽𝙳𝙴𝚇_𝙹 = 𝙹_{k}) \land (𝚅𝙰𝙻𝚄𝙴 = 𝚅_{k})) \Leftrightarrow S_{k}$ .

Figure 5.142.2. Automaton of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚖𝚊𝚝𝚛𝚒𝚡$ constraint

Figure 5.142.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚖𝚊𝚝𝚛𝚒𝚡$ constraint where $n$ and $m$ respectively stands for $𝙼𝙰𝚇_𝙸$ and $𝙼𝙰𝚇_𝙹$

Global Constraint Catalog

5. Global Constraint Catalogue

5.142. element_matrix

Figure 5.142.1. Initial and final graph of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚖𝚊𝚝𝚛𝚒𝚡$ constraint

Figure 5.142.2. Automaton of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚖𝚊𝚝𝚛𝚒𝚡$ constraint

Figure 5.142.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚖𝚊𝚝𝚛𝚒𝚡$ constraint where $n$ and $m$ respectively stands for $𝙼𝙰𝚇_𝙸$ and $𝙼𝙰𝚇_𝙹$

Global Constraint Catalog

5. Global Constraint Catalogue

5.142. element_matrix

Figure 5.142.1. Initial and final graph of the 𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚖𝚊𝚝𝚛𝚒𝚡 constraint

Figure 5.142.2. Automaton of the 𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚖𝚊𝚝𝚛𝚒𝚡 constraint

Figure 5.142.3. Hypergraph of the reformulation corresponding to the automaton of the 𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚖𝚊𝚝𝚛𝚒𝚡 constraint where n and m respectively stands for 𝙼𝙰𝚇_𝙸 and 𝙼𝙰𝚇_𝙹

Figure 5.142.1. Initial and final graph of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚖𝚊𝚝𝚛𝚒𝚡$ constraint

Figure 5.142.2. Automaton of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚖𝚊𝚝𝚛𝚒𝚡$ constraint

Figure 5.142.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚖𝚊𝚝𝚛𝚒𝚡$ constraint where $n$ and $m$ respectively stands for $𝙼𝙰𝚇_𝙸$ and $𝙼𝙰𝚇_𝙹$