Global Constraint Catalog: Cchange

5.65. change_vectors

DESCRIPTION

LINKS

Origin

Constraint

$𝚌𝚑𝚊𝚗𝚐𝚎_𝚟𝚎𝚌𝚝𝚘𝚛𝚜 (𝙽𝙲𝙷𝙰𝙽𝙶𝙴, 𝚅𝙴𝙲𝚃𝙾𝚁𝚂, 𝙲𝚃𝚁𝚂)$

Types

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

Arguments

$𝙽𝙲𝙷𝙰𝙽𝙶𝙴$	$𝚍𝚟𝚊𝚛$
$𝚅𝙴𝙲𝚃𝙾𝚁𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚎𝚌 - 𝚅𝙴𝙲𝚃𝙾𝚁)$
$𝙲𝚃𝚁𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚌𝚝𝚛 - 𝙲𝚃𝚁)$

Restrictions

| 𝚅𝙴𝙲𝚃𝙾𝚁 | \geq 1

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

𝙲𝚃𝚁 \in [=, \neq, <, \geq, >, \leq]

𝙽𝙲𝙷𝙰𝙽𝙶𝙴 \geq 0

𝙽𝙲𝙷𝙰𝙽𝙶𝙴 < | 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 |

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙴𝙲𝚃𝙾𝚁𝚂, 𝚟𝚎𝚌)

𝚜𝚊𝚖𝚎_𝚜𝚒𝚣𝚎

(𝚅𝙴𝙲𝚃𝙾𝚁𝚂, 𝚟𝚎𝚌)

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝙲𝚃𝚁𝚂, 𝚌𝚝𝚛)

| 𝙲𝚃𝚁𝚂 | = | 𝚅𝙴𝙲𝚃𝙾𝚁 |

Purpose

Let us note ${𝚅𝙴𝙲𝚃𝙾𝚁}_{1}, {𝚅𝙴𝙲𝚃𝙾𝚁}_{2}, \dots, {𝚅𝙴𝙲𝚃𝙾𝚁}_{n}$ the vectors of the $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ collection, and $d$ the number of components of each vector (all vectors have the same size). $𝙽𝙲𝙷𝙰𝙽𝙶𝙴$ is the number of times that the following disjunctions holds where $i \in [1, n - 1]$

$({𝚅𝙴𝙲𝚃𝙾𝚁}_{i} . 𝚟𝚎𝚌 [1] 𝙲𝚃𝚁𝚂 [1] {𝚅𝙴𝙲𝚃𝙾𝚁}_{i + 1} . 𝚟𝚎𝚌 [1]) \lor$

$({𝚅𝙴𝙲𝚃𝙾𝚁}_{i} . 𝚟𝚎𝚌 [2] 𝙲𝚃𝚁𝚂 [2] {𝚅𝙴𝙲𝚃𝙾𝚁}_{i + 1} . 𝚟𝚎𝚌 [2]) \lor$

$\dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \lor$

$({𝚅𝙴𝙲𝚃𝙾𝚁}_{i} . 𝚟𝚎𝚌 [d] 𝙲𝚃𝚁𝚂 [d] {𝚅𝙴𝙲𝚃𝙾𝚁}_{i + 1} . 𝚟𝚎𝚌 [d])$ .

Example

(\begin{matrix} 3, 〈\begin{matrix} 𝚟𝚎𝚌 - 〈4, 0〉, \\ 𝚟𝚎𝚌 - 〈4, 0〉, \\ 𝚟𝚎𝚌 - 〈4, 5〉, \\ 𝚟𝚎𝚌 - 〈3, 4〉, \\ 𝚟𝚎𝚌 - 〈3, 4〉, \\ 𝚟𝚎𝚌 - 〈3, 4〉, \\ 𝚟𝚎𝚌 - 〈4, 0〉 \end{matrix}〉, \\ 〈\neq, \neq〉 \end{matrix})

In the example we have the following 3 changes:

One change between $〈 4, 0 〉$ and $〈 4, 5 〉$ since $4 \neq 4 \lor 0 \neq 5$ ,
One change between $〈 4, 5 〉$ and $〈 3, 4 〉$ since $4 \neq 3 \lor 5 \neq 4$ ,
One change between $〈 3, 4 〉$ and $〈 4, 0 〉$ since $3 \neq 4 \lor 4 \neq 0$ .

Consequently the $𝚌𝚑𝚊𝚗𝚐𝚎_𝚟𝚎𝚌𝚝𝚘𝚛𝚜$ constraint holds since its first argument $𝙽𝙲𝙷𝙰𝙽𝙶𝙴$ is assigned value 3.

Typical

𝙲𝚃𝚁 \in [\neq]

| 𝚅𝙴𝙲𝚃𝙾𝚁 | > 1

𝙽𝙲𝙷𝙰𝙽𝙶𝙴 > 0

| 𝚅𝙴𝙲𝚃𝙾𝚁𝚂 | > 1

Arg. properties

Functional dependency: $𝙽𝙲𝙷𝙰𝙽𝙶𝙴$ determined by $𝚅𝙴𝙲𝚃𝙾𝚁𝚂$ and $𝙲𝚃𝚁𝚂$ .

See also

specialisation: $𝚌𝚑𝚊𝚗𝚐𝚎$ (vector replaced by $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ ), $𝚌𝚑𝚊𝚗𝚐𝚎_𝚙𝚊𝚒𝚛$ (vector replaced by $𝚙𝚊𝚒𝚛$ of $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜$ ).

Keywords

characteristic of a constraint: automaton, automaton with counters, vector.

constraint arguments: pure functional dependency.

constraint network structure: Berge-acyclic constraint network.

modelling: number of changes, functional dependency.

Global Constraint Catalog

5. Global Constraint Catalogue

5.65. change_vectors