Global Constraint Catalog: Cinterval_and

5.197. interval_and_count

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

[Cousin93]

Constraint

$𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕_𝚊𝚗𝚍_𝚌𝚘𝚞𝚗𝚝 (𝙰𝚃𝙼𝙾𝚂𝚃, 𝙲𝙾𝙻𝙾𝚄𝚁𝚂, 𝚃𝙰𝚂𝙺𝚂, 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻)$

Arguments

$𝙰𝚃𝙼𝙾𝚂𝚃$	$𝚒𝚗𝚝$
$𝙲𝙾𝙻𝙾𝚄𝚁𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚕 - 𝚒𝚗𝚝)$
$𝚃𝙰𝚂𝙺𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚘𝚛𝚒𝚐𝚒𝚗 - 𝚍𝚟𝚊𝚛, 𝚌𝚘𝚕𝚘𝚞𝚛 - 𝚍𝚟𝚊𝚛)$
$𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻$	$𝚒𝚗𝚝$

Restrictions

𝙰𝚃𝙼𝙾𝚂𝚃 \geq 0

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝙲𝙾𝙻𝙾𝚄𝚁𝚂, 𝚟𝚊𝚕)

𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝

(𝙲𝙾𝙻𝙾𝚄𝚁𝚂, 𝚟𝚊𝚕)

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚃𝙰𝚂𝙺𝚂, [𝚘𝚛𝚒𝚐𝚒𝚗, 𝚌𝚘𝚕𝚘𝚞𝚛])

𝚃𝙰𝚂𝙺𝚂 . 𝚘𝚛𝚒𝚐𝚒𝚗 \geq 0

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

Purpose

First consider the set of tasks of the $𝚃𝙰𝚂𝙺𝚂$ collection, where each task has a specific colour that may not be initially fixed. Then consider the intervals of the form $[k \cdot 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻, k \cdot 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 + 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 - 1]$ , where $k$ is an integer. The $𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕_𝚊𝚗𝚍_𝚌𝚘𝚞𝚗𝚝$ constraint forces that, for each interval $I_{k}$ previously defined, the total number of tasks, which both are assigned to $I_{k}$ and take their colour in $𝙲𝙾𝙻𝙾𝚄𝚁𝚂$ , does not exceed the limit $𝙰𝚃𝙼𝙾𝚂𝚃$ .

Example

(\begin{matrix} 2, 〈4〉, \\ 〈\begin{matrix} 𝚘𝚛𝚒𝚐𝚒𝚗 - 1 & 𝚌𝚘𝚕𝚘𝚞𝚛 - 4, \\ 𝚘𝚛𝚒𝚐𝚒𝚗 - 0 & 𝚌𝚘𝚕𝚘𝚞𝚛 - 9, \\ 𝚘𝚛𝚒𝚐𝚒𝚗 - 10 & 𝚌𝚘𝚕𝚘𝚞𝚛 - 4, \\ 𝚘𝚛𝚒𝚐𝚒𝚗 - 4 & 𝚌𝚘𝚕𝚘𝚞𝚛 - 4 \end{matrix}〉, 5 \end{matrix})

Figure 5.197.1 shows the solution associated with the example. The constraint $𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕_𝚊𝚗𝚍_𝚌𝚘𝚞𝚗𝚝$ holds since, for each interval, the number of tasks taking colour 4 does not exceed the limit 2.

Figure 5.197.1. The $𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕_𝚊𝚗𝚍_𝚌𝚘𝚞𝚗𝚝$ solution to the Example slot with the use of each interval

Typical

𝙰𝚃𝙼𝙾𝚂𝚃 > 0

𝙰𝚃𝙼𝙾𝚂𝚃 < | 𝚃𝙰𝚂𝙺𝚂 |

| 𝙲𝙾𝙻𝙾𝚄𝚁𝚂 | > 0

| 𝚃𝙰𝚂𝙺𝚂 | > 1

𝚛𝚊𝚗𝚐𝚎

(𝚃𝙰𝚂𝙺𝚂 . 𝚘𝚛𝚒𝚐𝚒𝚗) > 1

𝚛𝚊𝚗𝚐𝚎

(𝚃𝙰𝚂𝙺𝚂 . 𝚌𝚘𝚕𝚘𝚞𝚛) > 1

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

Symmetries

$𝙰𝚃𝙼𝙾𝚂𝚃$ can be increased.
Items of $𝙲𝙾𝙻𝙾𝚄𝚁𝚂$ are permutable.
Items of $𝚃𝙰𝚂𝙺𝚂$ are permutable.
One and the same constant can be added to the $𝚘𝚛𝚒𝚐𝚒𝚗$ attribute of all items of $𝚃𝙰𝚂𝙺𝚂$ .
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.
An occurrence of a value of $𝚃𝙰𝚂𝙺𝚂 . 𝚌𝚘𝚕𝚘𝚞𝚛$ that belongs to $𝙲𝙾𝙻𝙾𝚄𝚁𝚂 . 𝚟𝚊𝚕$ (resp. does not belong to $𝙲𝙾𝙻𝙾𝚄𝚁𝚂 . 𝚟𝚊𝚕$ ) can be replaced by any other value in $𝙲𝙾𝙻𝙾𝚄𝚁𝚂 . 𝚟𝚊𝚕$ (resp. not in $𝙲𝙾𝙻𝙾𝚄𝚁𝚂 . 𝚟𝚊𝚕$ ).

Arg. properties

Contractible wrt. $𝙲𝙾𝙻𝙾𝚄𝚁𝚂$ .
Contractible wrt. $𝚃𝙰𝚂𝙺𝚂$ .

Usage

This constraint was originally proposed for dealing with timetabling problems. In this context the different intervals are interpreted as morning and afternoon periods of different consecutive days. Each colour corresponds to a type of course (i.e., French, mathematics). There is a restriction on the maximum number of courses of a given type each morning as well as each afternoon.

Remark

If we want to only consider intervals that correspond to the morning or to the afternoon we could extend the $𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕_𝚊𝚗𝚍_𝚌𝚘𝚞𝚗𝚝$ constraint in the following way:

We introduce two extra parameters $𝚁𝙴𝚂𝚃$ and $𝚀𝚄𝙾𝚃𝙸𝙴𝙽𝚃$ that correspond to non-negative integers such that $𝚁𝙴𝚂𝚃$ is strictly less than $𝚀𝚄𝙾𝚃𝙸𝙴𝙽𝚃$ ,
We add the following condition to the arc constraint: $(𝚝𝚊𝚜𝚔𝚜 1 . 𝚘𝚛𝚒𝚐𝚒𝚗 / 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻) \equiv 𝚁𝙴𝚂𝚃 (\mod 𝚀𝚄𝙾𝚃𝙸𝙴𝙽𝚃)$

Now, if we want to express a constraint on the morning intervals, we set $𝚁𝙴𝚂𝚃$ to 0 and $𝚀𝚄𝙾𝚃𝙸𝙴𝙽𝚃$ to 2.

Reformulation

Let $K$ denote the index of the last possible interval where the tasks can be assigned: $K = ⌊ \frac{{max}_{i \in [1, | 𝚃𝙰𝚂𝙺𝚂 |]} (\bar{𝚃𝙰𝚂𝙺𝚂 [i] . 𝚘𝚛𝚒𝚐𝚒𝚗}) + 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 - 1}{𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻} ⌋$ . The $𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕_𝚊𝚗𝚍_𝚌𝚘𝚞𝚗𝚝$ $(𝙰𝚃𝙼𝙾𝚂𝚃, 𝙲𝙾𝙻𝙾𝚄𝚁𝚂, 𝚃𝙰𝚂𝙺𝚂, 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻)$ constraint can be expressed in term of a set of reified constraints and of $K$ arithmetic constraints (i.e., $𝚜𝚞𝚖_𝚌𝚝𝚛$ constraints).

For each task $𝚃𝙰𝚂𝙺𝚂 [i]$ $(i \in [1, | 𝚃𝙰𝚂𝙺𝚂 |])$ of the $𝚃𝙰𝚂𝙺𝚂$ collection we create a 0-1 variable $B_{i}$ that will be set to 1 if and only if task $𝚃𝙰𝚂𝙺𝚂 [i]$ takes a colour within the set of colours $𝙲𝙾𝙻𝙾𝚄𝚁𝚂$ :

$B_{i} \Leftrightarrow 𝚃𝙰𝚂𝙺𝚂 [i] . 𝚌𝚘𝚕𝚘𝚞𝚛 = 𝙲𝙾𝙻𝙾𝚄𝚁𝚂 [1] . 𝚟𝚊𝚕 \lor$

        $𝚃𝙰𝚂𝙺𝚂 [i] . 𝚌𝚘𝚕𝚘𝚞𝚛 = 𝙲𝙾𝙻𝙾𝚄𝚁𝚂 [2] . 𝚟𝚊𝚕 \lor$

        $\dots \dots \dots \dots \dots \dots \dots \dots \dots \dots$

        $𝚃𝙰𝚂𝙺𝚂 [i] . 𝚌𝚘𝚕𝚘𝚞𝚛 = 𝙲𝙾𝙻𝙾𝚄𝚁𝚂 [| 𝙲𝙾𝙻𝙾𝚄𝚁𝚂 |] . 𝚟𝚊𝚕$ .
For each task $𝚃𝙰𝚂𝙺𝚂 [i]$ $(i \in [1, | 𝚃𝙰𝚂𝙺𝚂 |])$ and for each interval $[k \cdot 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻, k \cdot 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 + 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 - 1]$ $(k \in [0, K])$ we create a 0-1 variable $B_{i k}$ that will be set to 1 if and only if, both task $𝚃𝙰𝚂𝙺𝚂 [i]$ takes a colour within the set of colours $𝙲𝙾𝙻𝙾𝚄𝚁𝚂$ , and the origin of task $𝚃𝙰𝚂𝙺𝚂 [i]$ is assigned within interval $[k \cdot 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻, k \cdot 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 + 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 - 1]$ :

$B_{i k} \Leftrightarrow B_{i} \land$

$𝚃𝙰𝚂𝙺𝚂 [i] . 𝚘𝚛𝚒𝚐𝚒𝚗 \geq k \cdot 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 \land$

$𝚃𝙰𝚂𝙺𝚂 [i] . 𝚘𝚛𝚒𝚐𝚒𝚗 \leq k \cdot 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 + 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 - 1$
Finally, for each interval $[k \cdot 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻, k \cdot 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 + 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 - 1]$ $(k \in [0, K])$ , we impose the sum $B_{1 k} + B_{2 k} + \dots + B_{| 𝚃𝙰𝚂𝙺𝚂 | k}$ to not exceed the maximum allowed capacity $𝙰𝚃𝙼𝙾𝚂𝚃$ .

See also

assignment dimension removed: $𝚊𝚖𝚘𝚗𝚐_𝚕𝚘𝚠_𝚞𝚙$ (assignment dimension corresponding to intervals is removed).

used in graph description: $𝚊𝚖𝚘𝚗𝚐_𝚕𝚘𝚠_𝚞𝚙$ .

Keywords

application area: assignment.

characteristic of a constraint: coloured, automaton, automaton with array of counters.

constraint type: timetabling constraint, resource constraint, temporal constraint.

modelling: assignment dimension, interval.

Arc input(s)

$𝚃𝙰𝚂𝙺𝚂$ $𝚃𝙰𝚂𝙺𝚂$

Arc generator

𝑃𝑅𝑂𝐷𝑈𝐶𝑇

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

Arc arity

Arc constraint(s)

𝚝𝚊𝚜𝚔𝚜 1 . 𝚘𝚛𝚒𝚐𝚒𝚗 / 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻 = 𝚝𝚊𝚜𝚔𝚜 2 . 𝚘𝚛𝚒𝚐𝚒𝚗 / 𝚂𝙸𝚉𝙴_𝙸𝙽𝚃𝙴𝚁𝚅𝙰𝙻

Sets

\begin{matrix} 𝖲𝖴𝖢𝖢 \mapsto \\ [\begin{matrix} 𝚜𝚘𝚞𝚛𝚌𝚎, \\ 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 - 𝚌𝚘𝚕 (\begin{matrix} 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 - 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛), \\ 𝚒𝚝𝚎𝚖 (𝚟𝚊𝚛 - 𝚃𝙰𝚂𝙺𝚂 . 𝚌𝚘𝚕𝚘𝚞𝚛)] \end{matrix}) \end{matrix}] \end{matrix}

Constraint(s) on sets

𝚊𝚖𝚘𝚗𝚐_𝚕𝚘𝚠_𝚞𝚙

(0, 𝙰𝚃𝙼𝙾𝚂𝚃, 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜, 𝙲𝙾𝙻𝙾𝚄𝚁𝚂)

Graph model

We use a bipartite graph where each class of vertices corresponds to the different tasks of the $𝚃𝙰𝚂𝙺𝚂$ collection. There is an arc between two tasks if their origins belong to the same interval. Finally we enforce an $𝚊𝚖𝚘𝚗𝚐_𝚕𝚘𝚠_𝚞𝚙$ constraint on each set $𝒮$ of successors of the different vertices of the final graph. This put a restriction on the maximum number of tasks of $𝒮$ for which the colour attribute takes its value in $𝙲𝙾𝙻𝙾𝚄𝚁𝚂$ .

Parts (A) and (B) of Figure 5.197.2 respectively show the initial and final graph associated with the Example slot. Each connected component of the final graph corresponds to items that are all assigned to the same interval.

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


(a)	(b)

Automaton: Figure 5.197.3 depicts the automaton associated with the $𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕_𝚊𝚗𝚍_𝚌𝚘𝚞𝚗𝚝$ constraint. Let ${𝙲𝙾𝙻𝙾𝚄𝚁}_{i}$ be the $𝚌𝚘𝚕𝚘𝚞𝚛$ attribute of the $i^{t h}$ item of the $𝚃𝙰𝚂𝙺𝚂$ collection. To each pair $(𝙲𝙾𝙻𝙾𝚄𝚁𝚂, {𝙲𝙾𝙻𝙾𝚄𝚁}_{i})$ corresponds a signature variable $S_{i}$ as well as the following signature constraint: ${𝙲𝙾𝙻𝙾𝚄𝚁}_{i} \in 𝙲𝙾𝙻𝙾𝚄𝚁𝚂 \Leftrightarrow S_{i}$ .

Figure 5.197.3. Automaton of the $𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕_𝚊𝚗𝚍_𝚌𝚘𝚞𝚗𝚝$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.197. interval_and_count

Figure 5.197.1. The $𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕_𝚊𝚗𝚍_𝚌𝚘𝚞𝚗𝚝$ solution to the Example slot with the use of each interval

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

Figure 5.197.3. Automaton of the $𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕_𝚊𝚗𝚍_𝚌𝚘𝚞𝚗𝚝$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.197. interval_and_count

Figure 5.197.1. The 𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕_𝚊𝚗𝚍_𝚌𝚘𝚞𝚗𝚝 solution to the Example slot with the use of each interval

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

Figure 5.197.3. Automaton of the 𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕_𝚊𝚗𝚍_𝚌𝚘𝚞𝚗𝚝 constraint

Figure 5.197.1. The $𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕_𝚊𝚗𝚍_𝚌𝚘𝚞𝚗𝚝$ solution to the Example slot with the use of each interval

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

Figure 5.197.3. Automaton of the $𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕_𝚊𝚗𝚍_𝚌𝚘𝚞𝚗𝚝$ constraint