Global Constraint Catalog: Celem_from

5.138. elem_from_to

DESCRIPTION

LINKS

AUTOMATON

Origin

Derived from $𝚎𝚕𝚎𝚖$ .

Constraint

$𝚎𝚕𝚎𝚖_𝚏𝚛𝚘𝚖_𝚝𝚘 (𝙸𝚃𝙴𝙼, 𝚃𝙰𝙱𝙻𝙴)$

Synonym

$𝚎𝚕𝚎𝚖𝚎𝚗𝚝_𝚏𝚛𝚘𝚖_𝚝𝚘$ .

Arguments

$𝙸𝚃𝙴𝙼$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (\begin{matrix} 𝚏𝚛𝚘𝚖 - 𝚍𝚟𝚊𝚛, \\ 𝚌𝚜𝚝_𝚏𝚛𝚘𝚖 - 𝚒𝚗𝚝, \\ 𝚝𝚘 - 𝚍𝚟𝚊𝚛, \\ 𝚌𝚜𝚝_𝚝𝚘 - 𝚒𝚗𝚝, \\ 𝚟𝚊𝚕𝚞𝚎 - 𝚍𝚟𝚊𝚛 \end{matrix})$
$𝚃𝙰𝙱𝙻𝙴$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚒𝚗𝚍𝚎𝚡 - 𝚒𝚗𝚝, 𝚟𝚊𝚕𝚞𝚎 - 𝚍𝚟𝚊𝚛)$

Restrictions

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝙸𝚃𝙴𝙼, [𝚏𝚛𝚘𝚖, 𝚌𝚜𝚝_𝚏𝚛𝚘𝚖, 𝚝𝚘, 𝚌𝚜𝚝_𝚝𝚘, 𝚟𝚊𝚕𝚞𝚎])

𝙸𝚃𝙴𝙼 . 𝚏𝚛𝚘𝚖 \geq 1

𝙸𝚃𝙴𝙼 . 𝚏𝚛𝚘𝚖 \leq | 𝚃𝙰𝙱𝙻𝙴 |

𝙸𝚃𝙴𝙼 . 𝚝𝚘 \geq 1

𝙸𝚃𝙴𝙼 . 𝚝𝚘 \leq | 𝚃𝙰𝙱𝙻𝙴 |

𝙸𝚃𝙴𝙼 . 𝚏𝚛𝚘𝚖 \leq 𝙸𝚃𝙴𝙼 . 𝚝𝚘

| 𝙸𝚃𝙴𝙼 | = 1

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚃𝙰𝙱𝙻𝙴, [𝚒𝚗𝚍𝚎𝚡, 𝚟𝚊𝚕𝚞𝚎])

𝚃𝙰𝙱𝙻𝙴 . 𝚒𝚗𝚍𝚎𝚡 \geq 1

𝚃𝙰𝙱𝙻𝙴 . 𝚒𝚗𝚍𝚎𝚡 \leq | 𝚃𝙰𝙱𝙻𝙴 |

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

(𝚃𝙰𝙱𝙻𝙴, [𝚒𝚗𝚍𝚎𝚡])

Purpose

Let $𝙵𝚁𝙾𝙼$ , $𝙲𝚂𝚃_𝙵𝚁𝙾𝙼$ , $𝚃𝙾$ , $𝙲𝚂𝚃_𝚃𝙾$ , $𝚅𝙰𝙻𝚄𝙴$ respectively denote the attributes $𝙸𝚃𝙴𝙼 [1] . 𝚏𝚛𝚘𝚖$ , $𝙸𝚃𝙴𝙼 [1] . 𝚌𝚜𝚝_𝚏𝚛𝚘𝚖$ , $𝙸𝚃𝙴𝙼 [1] . 𝚝𝚘$ , $𝙸𝚃𝙴𝙼 [1] . 𝚌𝚜𝚝_𝚝𝚘$ , $𝙸𝚃𝙴𝙼 [1] . 𝚟𝚊𝚕𝚞𝚎$ of the unique item of the $𝙸𝚃𝙴𝙼$ collection.

Beside imposing the fact that $𝙵𝚁𝙾𝙼 \leq 𝚃𝙾$ and that both $𝙵𝚁𝙾𝙼$ and $𝚃𝙾$ are assigned a value in $[1, | 𝚃𝙰𝙱𝙻𝙴 |]$ , the $𝚎𝚕𝚎𝚖_𝚏𝚛𝚘𝚖_𝚝𝚘$ constraint forces the following condition: All entries of the $𝚃𝙰𝙱𝙻𝙴$ collection from position $max (1, 𝙵𝚁𝙾𝙼 + 𝙲𝚂𝚃_𝙵𝚁𝙾𝙼)$ to position $min (| 𝚃𝙰𝙱𝙻𝙴 |, 𝚃𝙾 + 𝙲𝚂𝚃_𝚃𝙾)$ are equal to $𝚅𝙰𝙻𝚄𝙴$ . When $max (1, 𝙵𝚁𝙾𝙼 + 𝙲𝚂𝚃_𝙵𝚁𝙾𝙼)$ is strictly greater than $min (| 𝚃𝙰𝙱𝙻𝙴 |, 𝚃𝙾 + 𝙲𝚂𝚃_𝚃𝙾)$ the constraint holds no matter what value is assigned to $𝚅𝙰𝙻𝚄𝙴$ .

Example

(\begin{matrix} 〈𝚏𝚛𝚘𝚖 - 1 𝚌𝚜𝚝_𝚏𝚛𝚘𝚖 - 1 𝚝𝚘 - 4 𝚌𝚜𝚝_𝚝𝚘 - - 1 𝚟𝚊𝚕𝚞𝚎 - 2〉, \\ 〈\begin{matrix} 𝚒𝚗𝚍𝚎𝚡 - 1 & 𝚟𝚊𝚕𝚞𝚎 - 6, \\ 𝚒𝚗𝚍𝚎𝚡 - 2 & 𝚟𝚊𝚕𝚞𝚎 - 2, \\ 𝚒𝚗𝚍𝚎𝚡 - 3 & 𝚟𝚊𝚕𝚞𝚎 - 2, \\ 𝚒𝚗𝚍𝚎𝚡 - 4 & 𝚟𝚊𝚕𝚞𝚎 - 9, \\ 𝚒𝚗𝚍𝚎𝚡 - 5 & 𝚟𝚊𝚕𝚞𝚎 - 9 \end{matrix}〉 \end{matrix})

The $𝚎𝚕𝚎𝚖_𝚏𝚛𝚘𝚖_𝚝𝚘$ constraint holds since all entries between position $max (1, 𝙵𝚁𝙾𝙼 + 𝙲𝚂𝚃_𝙵𝚁𝙾𝙼) = max (1, 1 + 1) = 2$ and position $min (| 𝚃𝙰𝙱𝙻𝙴 |, 𝚃𝙾 + 𝙲𝚂𝚃_𝚃𝙾) = min (5, 4 - 1) = 3$ are equal to 2.

Typical

𝙸𝚃𝙴𝙼 . 𝚌𝚜𝚝_𝚏𝚛𝚘𝚖 \geq 0

𝙸𝚃𝙴𝙼 . 𝚌𝚜𝚝_𝚏𝚛𝚘𝚖 \leq 1

𝙸𝚃𝙴𝙼 . 𝚌𝚜𝚝_𝚝𝚘 \geq - 1

𝙸𝚃𝙴𝙼 . 𝚌𝚜𝚝_𝚝𝚘 \leq 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.

Usage

Given an array $t [1 . . n]$ of integers (i.e., an array of integers for which the entries are defined between 1 and $n$ ), the $𝚎𝚕𝚎𝚖_𝚏𝚛𝚘𝚖_𝚝𝚘$ constraint is for instance useful for encoding expressions of the form $\exists i \in [1, n], \forall j \in [i + 1, n] | t [i] = 0$ . Note that, when the interval $[i + 1, n]$ is empty, the condition $\forall j \in [i + 1, n] | t [i] = 0$ is satisfied and $i$ is equal to $n$ . This example is encoded by using an $𝚎𝚕𝚎𝚖_𝚏𝚛𝚘𝚖_𝚝𝚘$ constraint and by respectively setting:

$𝙵𝚁𝙾𝙼$ to $i$ , where $i$ is a variable that is assigned a value from interval $[1, n]$ ,
$𝙲𝚂𝚃_𝙵𝚁𝙾𝙼$ to constant 1,
$𝚃𝙾$ to $n$ , the index of the last entry of the array $t [1 . . n]$ ,
$𝙲𝚂𝚃_𝚃𝙾$ to constant 0,
$𝚅𝙰𝙻𝚄𝙴$ to 0, the value we are looking for.
$𝚃𝙰𝙱𝙻𝙴$ to the array of integers $t [1 . . n]$ .

Finally, note that $j$ is not used at all.

Keywords

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

constraint type: data constraint.

filtering: arc-consistency.

modelling: array constraint, table, variable indexing, variable subscript.

Automaton

Figure 5.138.1 depicts the automaton associated with the $𝚎𝚕𝚎𝚖_𝚏𝚛𝚘𝚖_𝚝𝚘$ constraint.

Let us first introduce some notations:

Let $n$ denote the number of items of the $𝚃𝙰𝙱𝙻𝙴$ collection.
Let ${𝙸𝙽𝙳𝙴𝚇}_{i}$ and ${𝚅𝙰𝙻𝚄𝙴}_{i}$ respectively be the $𝚒𝚗𝚍𝚎𝚡$ and the $𝚟𝚊𝚕𝚞𝚎$ attributes of the $i^{t h}$ item of the $𝚃𝙰𝙱𝙻𝙴$ collection.
Let $𝙵𝚁𝙾𝙼$ , $𝙲𝚂𝚃_𝙵𝚁𝙾𝙼$ , $𝚃𝙾$ , $𝙲𝚂𝚃_𝚃𝙾$ , $𝚅𝙰𝙻𝚄𝙴$ respectively denote the attributes $𝙸𝚃𝙴𝙼 [1] . 𝚏𝚛𝚘𝚖$ , $𝙸𝚃𝙴𝙼 [1] . 𝚌𝚜𝚝_𝚏𝚛𝚘𝚖$ , $𝙸𝚃𝙴𝙼 [1] . 𝚝𝚘$ , $𝙸𝚃𝙴𝙼 [1] . 𝚌𝚜𝚝_𝚝𝚘$ , $𝙸𝚃𝙴𝙼 [1] . 𝚟𝚊𝚕𝚞𝚎$ of the unique item of the $𝙸𝚃𝙴𝙼$ collection.
Let $𝙸𝙽$ be a shortcut for condition $1 \leq 𝙵𝚁𝙾𝙼 \land 𝙵𝚁𝙾𝙼 \leq 𝚃𝙾 \land 𝚃𝙾 \leq n$ .
Let $𝙵$ and $𝚃$ respectively denote the quantities $max (1, 𝙵𝚁𝙾𝙼 + 𝙲𝚂𝚃_𝙵𝚁𝙾𝙼)$ and $min (| 𝚃𝙰𝙱𝙻𝙴 |, 𝚃𝙾 + 𝙲𝚂𝚃_𝚃𝙾)$ .

To each septuple $(𝙵𝚁𝙾𝙼, 𝚃𝙾, 𝙵, 𝚃, 𝚅𝙰𝙻𝚄𝙴, {𝙸𝙽𝙳𝙴𝚇}_{i}, {𝚅𝙰𝙻𝚄𝙴}_{i})$ corresponds a signature variable $S_{i}$ as well as the following signature constraint:

$\{\begin{matrix} (𝙸𝙽 \land 𝙵 > 𝚃) & \Leftrightarrow S_{i} = 0 \land \\ (𝙸𝙽 \land 𝙵 \leq 𝚃 \land 𝙵 > {𝙸𝙽𝙳𝙴𝚇}_{i}) & \Leftrightarrow S_{i} = 1 \land \\ (𝙸𝙽 \land 𝙵 \leq 𝚃 \land 𝚃 < {𝙸𝙽𝙳𝙴𝚇}_{i}) & \Leftrightarrow S_{i} = 2 \land \\ (𝙸𝙽 \land 𝙵 \leq 𝚃 \land 𝙵 \leq {𝙸𝙽𝙳𝙴𝚇}_{i} \land {𝙸𝙽𝙳𝙴𝚇}_{i} \leq 𝚃 \land 𝚅𝙰𝙻𝚄𝙴 = {𝚅𝙰𝙻𝚄𝙴}_{i}) & \Leftrightarrow S_{i} = 3 \land \\ (𝙸𝙽 \land 𝙵 \leq 𝚃 \land 𝙵 \leq {𝙸𝙽𝙳𝙴𝚇}_{i} \land {𝙸𝙽𝙳𝙴𝚇}_{i} \leq 𝚃 \land 𝚅𝙰𝙻𝚄𝙴 \neq {𝚅𝙰𝙻𝚄𝙴}_{i}) & \Leftrightarrow S_{i} = 4 \end{matrix}$ .

Figure 5.138.1. Automaton of the $𝚎𝚕𝚎𝚖_𝚏𝚛𝚘𝚖_𝚝𝚘$ constraint

Figure 5.138.2. Hypergraph of the reformulation corresponding to the automaton of the $𝚎𝚕𝚎𝚖_𝚏𝚛𝚘𝚖_𝚝𝚘$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.138. elem_from_to

Figure 5.138.1. Automaton of the 𝚎𝚕𝚎𝚖_𝚏𝚛𝚘𝚖_𝚝𝚘 constraint

Figure 5.138.2. Hypergraph of the reformulation corresponding to the automaton of the 𝚎𝚕𝚎𝚖_𝚏𝚛𝚘𝚖_𝚝𝚘 constraint

Figure 5.138.1. Automaton of the $𝚎𝚕𝚎𝚖_𝚏𝚛𝚘𝚖_𝚝𝚘$ constraint

Figure 5.138.2. Hypergraph of the reformulation corresponding to the automaton of the $𝚎𝚕𝚎𝚖_𝚏𝚛𝚘𝚖_𝚝𝚘$ constraint