Global Constraint Catalog: Ccommon

5.76. common_interval

DESCRIPTION

LINKS

GRAPH

Origin

Constraint

$𝚌𝚘𝚖𝚖𝚘𝚗_𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕 (\begin{matrix} 𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1, \\ 𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2, \\ 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1, \\ 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2, \\ 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 \end{matrix})$

Arguments

$𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1$	$𝚍𝚟𝚊𝚛$
$𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2$	$𝚍𝚟𝚊𝚛$
$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$
$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$
$𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻$	$𝚒𝚗𝚝$

Restrictions

𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1 \geq 0

𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1 \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 |

𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2 \geq 0

𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2 \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 |

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1, 𝚟𝚊𝚛)

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2, 𝚟𝚊𝚛)

𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 > 0

Purpose

$𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1$ is the number of variables of the collection of variables $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ taking a value in one of the intervals derived from the values assigned to the variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ : To each value $v$ assigned to a variable of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ we associate the interval $[𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 \cdot ⌊ v / 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 ⌋, 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 \cdot ⌊ v / 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 ⌋ + 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 - 1]$ .

$𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2$ is the number of variables of the collection of variables $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ taking a value in one of the intervals derived from the values assigned to the variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ : To each value $v$ assigned to a variable of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ we associate the interval $[𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 \cdot ⌊ v / 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 ⌋, 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 \cdot ⌊ v / 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 ⌋ + 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 - 1]$ .

Example

(3, 2, 〈8, 6, 6, 0〉, 〈7, 3, 3, 3, 3, 7〉, 3)

In the example, the last argument $𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 = 3$ defines the following family of intervals $[3 \cdot k, 3 \cdot k + 2]$ , where $k$ is an integer. As a consequence the items of collection $〈 8, 6, 6, 0 〉$ respectively correspond to intervals $[6, 8]$ , $[6, 8]$ , $[6, 8]$ and $[0, 2]$ . Similarly the items of collection $〈 7, 3, 3, 3, 3, 7 〉$ respectively correspond to intervals $[6, 8]$ , $[3, 5]$ , $[3, 5]$ , $[3, 5]$ , $[3, 5]$ , $[6, 8]$ . The $𝚌𝚘𝚖𝚖𝚘𝚗_𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕$ constraint holds since:

Its first argument $𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1 = 3$ is the number of intervals associated with the items of collection $〈 8, 6, 6, 0 〉$ that also correspond to intervals associated with $〈 7, 3, 3, 3, 3, 7 〉$ .
Its second argument $𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2 = 2$ is the number of intervals associated with the items of collection $〈 7, 3, 3, 3, 3, 7 〉$ that also correspond to intervals associated with $〈 8, 6, 6, 0 〉$ .

Typical

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 | > 1

𝚛𝚊𝚗𝚐𝚎

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 . 𝚟𝚊𝚛) > 1

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 | > 1

𝚛𝚊𝚗𝚐𝚎

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 . 𝚟𝚊𝚛) > 1

𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 > 1

𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 <

𝚛𝚊𝚗𝚐𝚎

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 . 𝚟𝚊𝚛)

𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 <

𝚛𝚊𝚗𝚐𝚎

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 . 𝚟𝚊𝚛)

Symmetries

Arguments are permutable w.r.t. permutation $(𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1, 𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2)$ $(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2)$ $(𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻)$ .
Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ are permutable.
Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ are permutable.
An occurrence of a value of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1 . 𝚟𝚊𝚛$ that belongs to the $k$ -th interval, of size $𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻$ , can be replaced by any other value of the same interval.
An occurrence of a value of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2 . 𝚟𝚊𝚛$ that belongs to the $k$ -th interval, of size $𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻$ , can be replaced by any other value of the same interval.

Arg. properties

Functional dependency: $𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1$ determined by $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ , $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ and $𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻$ .
Functional dependency: $𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2$ determined by $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ , $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$ and $𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻$ .

See also

specialisation: $𝚌𝚘𝚖𝚖𝚘𝚗$ ( $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎 / 𝚌𝚘𝚗𝚜𝚝𝚊𝚗𝚝$ replaced by $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ ).

Keywords

constraint arguments: constraint between two collections of variables, pure functional dependency.

final graph structure: acyclic, bipartite, no loop.

modelling: interval, functional dependency.

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 1$ $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 2$

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

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

Arc arity

Arc constraint(s)

\begin{matrix} 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1 . 𝚟𝚊𝚛 / 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 = \\ 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2 . 𝚟𝚊𝚛 / 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 \end{matrix}

Graph property(ies)

•

𝐍𝐒𝐎𝐔𝐑𝐂𝐄

= 𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1

•

𝐍𝐒𝐈𝐍𝐊

= 𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2

Graph class

•

𝙰𝙲𝚈𝙲𝙻𝙸𝙲

•

𝙱𝙸𝙿𝙰𝚁𝚃𝙸𝚃𝙴

•

𝙽𝙾_𝙻𝙾𝙾𝙿

Graph model

Parts (A) and (B) of Figure 5.76.1 respectively show the initial and final graph associated with the Example slot. Since we use the $𝐍𝐒𝐎𝐔𝐑𝐂𝐄$ and $𝐍𝐒𝐈𝐍𝐊$ graph properties, the source and sink vertices of the final graph are stressed with a double circle. Since the graph has only 3 sources and 2 sinks the variables $𝙽𝙲𝙾𝙼𝙼𝙾𝙽 1$ and $𝙽𝙲𝙾𝙼𝙼𝙾𝙽 2$ are respectively equal to 3 and 2. Note that the vertices corresponding to the variables that take values 0 or 3 were removed from the final graph since there is no arc for which the associated arc constraint holds.

Figure 5.76.1. Initial and final graph of the $𝚌𝚘𝚖𝚖𝚘𝚗_𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕$ constraint


(a)	(b)

Global Constraint Catalog

5. Global Constraint Catalogue

5.76. common_interval

Figure 5.76.1. Initial and final graph of the 𝚌𝚘𝚖𝚖𝚘𝚗_𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕 constraint

Figure 5.76.1. Initial and final graph of the $𝚌𝚘𝚖𝚖𝚘𝚗_𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕$ constraint