Global Constraint Catalog: Cninterval

5.277. ninterval

DESCRIPTION

LINKS

GRAPH

Origin

Derived from $𝚗𝚟𝚊𝚕𝚞𝚎$ .

Constraint

$𝚗𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕 (𝙽𝚅𝙰𝙻, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻)$

Arguments

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

Restrictions

𝙽𝚅𝙰𝙻 \geq 𝚖𝚒𝚗 (1, | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |)

𝙽𝚅𝙰𝙻 \leq | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

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

Purpose

Consider the intervals of the form $[𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 \cdot k, 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 \cdot k + 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 - 1]$ where $k$ is an integer. $𝙽𝚅𝙰𝙻$ is the number of intervals for which at least one value is assigned to at least one variable of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Example

(2, 〈3, 1, 9, 1, 9〉, 4)

In the example, the third argument $𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 = 4$ defines the following family of intervals $[4 \cdot k, 4 \cdot k + 3]$ , where $k$ is an integer. Values 3, 1, 9, 1 and 9 are respectively located within intervals $[0, 3]$ , $[0, 3]$ , $[8, 11]$ , $[0, 3]$ and $[8, 11]$ . Since we only use the two intervals $[0, 3]$ and $[8, 11]$ the first argument of the $𝚗𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕$ constraint is set to value 2.

Typical

𝙽𝚅𝙰𝙻 > 1

𝙽𝚅𝙰𝙻 < | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |

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

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

𝚛𝚊𝚗𝚐𝚎

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

(

𝚗𝚟𝚊𝚕

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) + 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 - 1) / 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 < 𝙽𝚅𝙰𝙻

Symmetries

Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ are permutable.
An occurrence of a value of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛$ that belongs to the $k$ -th interval, of size $𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻$ , can be replaced by any other value of the same interval.

Arg. properties

Functional dependency: $𝙽𝚅𝙰𝙻$ determined by $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ and $𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻$ .
Contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝙽𝚅𝙰𝙻 = 1$ and $| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | > 0$ .
Contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝙽𝚅𝙰𝙻 = | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 |$ .

Usage

The $𝚗𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕$ constraint is useful for counting the number of actually used periods, no matter how many time each period is used. A period can for example stand for a hour or for a day.

Algorithm

[Beldiceanu01], [BeldiceanuCarlssonThiel02].

See also

related: $𝚗𝚌𝚕𝚊𝚜𝚜$ ( $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎 / 𝚌𝚘𝚗𝚜𝚝𝚊𝚗𝚝$ replaced by $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎 \in 𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗$ ), $𝚗𝚎𝚚𝚞𝚒𝚟𝚊𝚕𝚎𝚗𝚌𝚎$ ( $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎 / 𝚌𝚘𝚗𝚜𝚝𝚊𝚗𝚝$ replaced by $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎 \mod 𝚌𝚘𝚗𝚜𝚝𝚊𝚗𝚝$ ), $𝚗𝚙𝚊𝚒𝚛$ ( $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎 / 𝚌𝚘𝚗𝚜𝚝𝚊𝚗𝚝$ replaced by $𝚙𝚊𝚒𝚛$ of $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜$ ).

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

Keywords

constraint arguments: pure functional dependency.

constraint type: counting constraint, value partitioning constraint.

final graph structure: strongly connected component, equivalence.

modelling: number of distinct equivalence classes, interval, functional dependency.

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$

Arc generator

𝐶𝐿𝐼𝑄𝑈𝐸

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

Arc arity

Arc constraint(s)

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

Graph property(ies)

𝐍𝐒𝐂𝐂

= 𝙽𝚅𝙰𝙻

Graph model

Parts (A) and (B) of Figure 5.277.1 respectively show the initial and final graph associated with the Example slot. Since we use the $𝐍𝐒𝐂𝐂$ graph property we show the different strongly connected components of the final graph. Each strongly connected component corresponds to those values of an interval that are assigned to some variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection. The values 1, 3 and the value 9, which respectively correspond to intervals $[0, 3]$ and $[8, 11]$ , are assigned to the variables of the $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ collection.

Figure 5.277.1. Initial and final graph of the $𝚗𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕$ constraint


(a)	(b)

Global Constraint Catalog

5. Global Constraint Catalogue

5.277. ninterval

Figure 5.277.1. Initial and final graph of the 𝚗𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕 constraint

Figure 5.277.1. Initial and final graph of the $𝚗𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕$ constraint