## 5.413. used_by_interval

Origin
Constraint

$\mathrm{𝚞𝚜𝚎𝚍}_\mathrm{𝚋𝚢}_\mathrm{𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕}\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1},\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2},\mathrm{𝚂𝙸𝚉𝙴}_\mathrm{𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻}\right)$

Arguments
 $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$ $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$ $\mathrm{𝚂𝙸𝚉𝙴}_\mathrm{𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻}$ $\mathrm{𝚒𝚗𝚝}$
Restrictions
 $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}|\ge |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}|$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1},\mathrm{𝚟𝚊𝚛}\right)$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2},\mathrm{𝚟𝚊𝚛}\right)$ $\mathrm{𝚂𝙸𝚉𝙴}_\mathrm{𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻}>0$
Purpose

Let ${N}_{i}$ (respectively ${M}_{i}$) denote the number of variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}$ (respectively $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}$) that take a value in the interval $\left[\mathrm{𝚂𝙸𝚉𝙴}_\mathrm{𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻}·i,\mathrm{𝚂𝙸𝚉𝙴}_\mathrm{𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻}·i+\mathrm{𝚂𝙸𝚉𝙴}_\mathrm{𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻}-1\right]$. For all integer $i$ we have ${M}_{i}>0⇒{N}_{i}\ge {M}_{i}$.

Example
$\left(〈1,9,1,8,6,2〉,〈1,0,7,7〉,3\right)$

In the example, the third argument $\mathrm{𝚂𝙸𝚉𝙴}_\mathrm{𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻}=3$ defines the following family of intervals $\left[3·k,3·k+2\right]$, where $k$ is an integer. Consequently the values of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}=〈1,0,7,7〉$ are respectively located within intervals $\left[0,2\right]$, $\left[0,2\right]$, $\left[6,8\right]$, $\left[6,8\right]$. Therefore intervals $\left[0,2\right]$ and $\left[6,8\right]$ are respectively used 2 and 2 times.

Similarly, the values of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}=〈1,9,1,8,6,2〉$ are respectively located within intervals $\left[0,2\right]$, $\left[9,11\right]$, $\left[0,2\right]$, $\left[6,8\right]$, $\left[6,8\right]$, $\left[0,2\right]$. Therefore intervals $\left[0,2\right]$, $\left[6,8\right]$ and $\left[9,11\right]$ are respectively used 3, 2 and 1 times.

Consequently, the $\mathrm{𝚞𝚜𝚎𝚍}_\mathrm{𝚋𝚢}_\mathrm{𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕}$ constraint holds since, for each interval associated with the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}=〈1,0,7,7〉$, its number of occurrences within $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}=〈1,9,1,8,6,2〉$ is greater than or equal to its number of occurrences within $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}$:

• Interval $\left[0,2\right]$ occurs 3 times within $〈1,9,1,8,6,2〉$ and 2 times within $〈1,0,7,7〉$.

• Interval $\left[6,8\right]$ occurs 2 times within $〈1,9,1,8,6,2〉$ and 2 times within $〈1,0,7,7〉$.

Typical
 $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}|>1$ $\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}.\mathrm{𝚟𝚊𝚛}\right)>1$ $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}|>1$ $\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}.\mathrm{𝚟𝚊𝚛}\right)>1$ $\mathrm{𝚂𝙸𝚉𝙴}_\mathrm{𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻}>1$ $\mathrm{𝚂𝙸𝚉𝙴}_\mathrm{𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻}<$$\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}.\mathrm{𝚟𝚊𝚛}\right)$ $\mathrm{𝚂𝙸𝚉𝙴}_\mathrm{𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻}<$$\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}.\mathrm{𝚟𝚊𝚛}\right)$
Symmetries
• Items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}$ are permutable.

• Items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}$ are permutable.

• An occurrence of a value of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}.\mathrm{𝚟𝚊𝚛}$ that belongs to the $k$-th interval, of size $\mathrm{𝚂𝙸𝚉𝙴}_\mathrm{𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻}$, can be replaced by any other value of the same interval.

• An occurrence of a value of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}.\mathrm{𝚟𝚊𝚛}$ that belongs to the $k$-th interval, of size $\mathrm{𝚂𝙸𝚉𝙴}_\mathrm{𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻}$, can be replaced by any other value of the same interval.

Arg. properties
• Contractible wrt. $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}$.

• Extensible wrt. $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}$.

• Aggregate: $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}\left(\mathrm{𝚞𝚗𝚒𝚘𝚗}\right)$, $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}\left(\mathrm{𝚞𝚗𝚒𝚘𝚗}\right)$, $\mathrm{𝚂𝙸𝚉𝙴}_\mathrm{𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻}\left(\mathrm{𝚒𝚍}\right)$.

Reformulation

The $\mathrm{𝚞𝚜𝚎𝚍}_\mathrm{𝚋𝚢}_\mathrm{𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕}$$\left(〈\mathrm{𝚟𝚊𝚛}-{U}_{1}\mathrm{𝚟𝚊𝚛}-{U}_{2},\cdots ,\mathrm{𝚟𝚊𝚛}-{U}_{|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}|}〉,〈\mathrm{𝚟𝚊𝚛}-{V}_{1}\mathrm{𝚟𝚊𝚛}-{V}_{2},\cdots ,\mathrm{𝚟𝚊𝚛}-{V}_{|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}|}〉,\mathrm{𝚂𝙸𝚉𝙴}_\mathrm{𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻}\right)$ constraint can be expressed by introducing $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}|+|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}|$ quotient variables

${U}_{i}=\mathrm{𝚂𝙸𝚉𝙴}_\mathrm{𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻}·{P}_{i}+{R}_{i}$, ${R}_{i}\in \left[0,\mathrm{𝚂𝙸𝚉𝙴}_\mathrm{𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻}-1\right]$ $\left(i\in \left[1,|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}|\right]\right)$,

${V}_{i}=\mathrm{𝚂𝙸𝚉𝙴}_\mathrm{𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻}·{Q}_{i}+{S}_{i}$, ${S}_{i}\in \left[0,\mathrm{𝚂𝙸𝚉𝙴}_\mathrm{𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻}-1\right]$ $\left(i\in \left[1,|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}|\right]\right)$,

in term of a conjunction of $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}|$ reified constraints of the form:

${\sum }_{1\le j\le |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}|}\left({Q}_{i}={P}_{j}\right)\ge {\sum }_{1\le j\le |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}|}\left({Q}_{i}={Q}_{j}\right)$ $\left(i\in \left[1,|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}|\right]\right)$.

Used in

specialisation: $\mathrm{𝚞𝚜𝚎𝚍}_\mathrm{𝚋𝚢}$ ($\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}/\mathrm{𝚌𝚘𝚗𝚜𝚝𝚊𝚗𝚝}$ replaced by $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$).

Keywords
Arc input(s)

$\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{1}$ $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}$

Arc generator
$\mathrm{𝑃𝑅𝑂𝐷𝑈𝐶𝑇}$$↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1},\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}\right)$

Arc arity
Arc constraint(s)
$\begin{array}{c}\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1}.\mathrm{𝚟𝚊𝚛}/\mathrm{𝚂𝙸𝚉𝙴}_\mathrm{𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻}=\hfill \\ \mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}.\mathrm{𝚟𝚊𝚛}/\mathrm{𝚂𝙸𝚉𝙴}_\mathrm{𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻}\hfill \end{array}$
Graph property(ies)
 $•\text{for}\text{all}\text{connected}\text{components:}$$\mathrm{𝐍𝐒𝐎𝐔𝐑𝐂𝐄}$$\ge$$\mathrm{𝐍𝐒𝐈𝐍𝐊}$ $•$$\mathrm{𝐍𝐒𝐈𝐍𝐊}$$=|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}|$

Graph model

Parts (A) and (B) of Figure 5.413.1 respectively show the initial and final graph associated with the Example slot. Since we use the $\mathrm{𝐍𝐒𝐎𝐔𝐑𝐂𝐄}$ and $\mathrm{𝐍𝐒𝐈𝐍𝐊}$ graph properties, the source and sink vertices of the final graph are stressed with a double circle. Since there is a constraint on each connected component of the final graph we also show the different connected components. Each of them corresponds to an equivalence class according to the arc constraint. Note that the vertex corresponding to the variable that takes value 9 was removed from the final graph since there is no arc for which the associated equivalence constraint holds. The $\mathrm{𝚞𝚜𝚎𝚍}_\mathrm{𝚋𝚢}_\mathrm{𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕}$ constraint holds since:

• For each connected component of the final graph the number of sources is greater than or equal to the number of sinks.

• The number of sinks of the final graph is equal to $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\mathtt{2}|$.

Signature

Since the initial graph contains only sources and sinks, and since sources of the initial graph cannot become sinks of the final graph, we have that the maximum number of sinks of the final graph is equal to $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}2|$. Therefore we can rewrite $\mathrm{𝐍𝐒𝐈𝐍𝐊}=|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}2|$ to $\mathrm{𝐍𝐒𝐈𝐍𝐊}\ge |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}2|$ and simplify $\underline{\overline{\mathrm{𝐍𝐒𝐈𝐍𝐊}}}$ to $\overline{\mathrm{𝐍𝐒𝐈𝐍𝐊}}$.