## 5.169. interval_and_sum

Origin
Constraint

$\mathrm{๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐}_\mathrm{๐๐๐}\left(\mathrm{๐๐ธ๐๐ด}_\mathrm{๐ธ๐ฝ๐๐ด๐๐ ๐ฐ๐ป},\mathrm{๐๐ฐ๐๐บ๐},\mathrm{๐ป๐ธ๐ผ๐ธ๐}\right)$

Arguments
 $\mathrm{๐๐ธ๐๐ด}_\mathrm{๐ธ๐ฝ๐๐ด๐๐ ๐ฐ๐ป}$ $\mathrm{๐๐๐}$ $\mathrm{๐๐ฐ๐๐บ๐}$ $\mathrm{๐๐๐๐๐๐๐๐๐๐}\left(\mathrm{๐๐๐๐๐๐}-\mathrm{๐๐๐๐},\mathrm{๐๐๐๐๐๐}-\mathrm{๐๐๐๐}\right)$ $\mathrm{๐ป๐ธ๐ผ๐ธ๐}$ $\mathrm{๐๐๐}$
Restrictions
 $\mathrm{๐๐ธ๐๐ด}_\mathrm{๐ธ๐ฝ๐๐ด๐๐ ๐ฐ๐ป}>0$ $\mathrm{๐๐๐๐๐๐๐๐}$$\left(\mathrm{๐๐ฐ๐๐บ๐},\left[\mathrm{๐๐๐๐๐๐},\mathrm{๐๐๐๐๐๐}\right]\right)$ $\mathrm{๐๐ฐ๐๐บ๐}.\mathrm{๐๐๐๐๐๐}โฅ0$ $\mathrm{๐ป๐ธ๐ผ๐ธ๐}โฅ0$
Purpose

A maximum resource capacity constraint: We have to fix the origins of a collection of tasks in such a way that, for all the tasks that are allocated to the same interval, the sum of the heights does not exceed a given capacity. All the intervals we consider have the following form: $\left[kยท\mathrm{๐๐ธ๐๐ด}_\mathrm{๐ธ๐ฝ๐๐ด๐๐ ๐ฐ๐ป},kยท\mathrm{๐๐ธ๐๐ด}_\mathrm{๐ธ๐ฝ๐๐ด๐๐ ๐ฐ๐ป}+\mathrm{๐๐ธ๐๐ด}_\mathrm{๐ธ๐ฝ๐๐ด๐๐ ๐ฐ๐ป}-1\right]$, where $k$ is an integer.

Example
$\left(\begin{array}{c}5,โฉ\begin{array}{cc}\mathrm{๐๐๐๐๐๐}-1\hfill & \mathrm{๐๐๐๐๐๐}-2,\hfill \\ \mathrm{๐๐๐๐๐๐}-10\hfill & \mathrm{๐๐๐๐๐๐}-2,\hfill \\ \mathrm{๐๐๐๐๐๐}-10\hfill & \mathrm{๐๐๐๐๐๐}-3,\hfill \\ \mathrm{๐๐๐๐๐๐}-4\hfill & \mathrm{๐๐๐๐๐๐}-1\hfill \end{array}โช,5\hfill \end{array}\right)$

Figureย 5.169.1 shows the solution associated with the example. The constraint $\mathrm{๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐}_\mathrm{๐๐๐}$ holds since the sum of the heights of the tasks that are located in the same interval does not exceed the limit 5. Each task $t$ is depicted by a rectangle $r$ associated with the interval to which the task $t$ is assigned. The rectangle $r$ is labelled with the position of $t$ within the items of the $\mathrm{๐๐ฐ๐๐บ๐}$ collection. The origin of task $t$ is represented by a small black square located within its corresponding rectangle $r$. Finally, the height of a rectangle $r$ is equal to the height of the task $t$ to which it corresponds.

Typical
 $\mathrm{๐๐ธ๐๐ด}_\mathrm{๐ธ๐ฝ๐๐ด๐๐ ๐ฐ๐ป}>1$ $|\mathrm{๐๐ฐ๐๐บ๐}|>1$ $\mathrm{๐๐๐๐๐}$$\left(\mathrm{๐๐ฐ๐๐บ๐}.\mathrm{๐๐๐๐๐๐}\right)>1$ $\mathrm{๐๐๐๐๐}$$\left(\mathrm{๐๐ฐ๐๐บ๐}.\mathrm{๐๐๐๐๐๐}\right)>1$ $\mathrm{๐ป๐ธ๐ผ๐ธ๐}<$$\mathrm{๐๐๐}$$\left(\mathrm{๐๐ฐ๐๐บ๐}.\mathrm{๐๐๐๐๐๐}\right)$
Symmetries
• Items of $\mathrm{๐๐ฐ๐๐บ๐}$ are permutable.

• One and the same constant can be added to the $\mathrm{๐๐๐๐๐๐}$ attribute of all items of $\mathrm{๐๐ฐ๐๐บ๐}$.

• An occurrence of a value of $\mathrm{๐๐ฐ๐๐บ๐}.\mathrm{๐๐๐๐๐๐}$ that belongs to the $k$-th interval, of size $\mathrm{๐๐ธ๐๐ด}_\mathrm{๐ธ๐ฝ๐๐ด๐๐ ๐ฐ๐ป}$, can be replaced by any other value of the same interval.

• $\mathrm{๐๐ฐ๐๐บ๐}.\mathrm{๐๐๐๐๐๐}$ can be decreased to any value $โฅ0$.

• $\mathrm{๐ป๐ธ๐ผ๐ธ๐}$ can be increased.

Usage

This constraint can be use for timetabling problems. In this context the different intervals are interpreted as morning and afternoon periods of different consecutive days. We have a capacity constraint for all tasks that are assigned to the same morning or afternoon of a given day.

Reformulation

Let $K$ denote the index of the last possible interval where the tasks can be assigned: $K=โ\frac{{max}_{iโ\left[1,|\mathrm{๐๐ฐ๐๐บ๐}|\right]}\left(\stackrel{ยฏ}{\mathrm{๐๐ฐ๐๐บ๐}\left[i\right].\mathrm{๐๐๐๐๐๐}}\right)+\mathrm{๐๐ธ๐๐ด}_\mathrm{๐ธ๐ฝ๐๐ด๐๐ ๐ฐ๐ป}-1}{\mathrm{๐๐ธ๐๐ด}_\mathrm{๐ธ๐ฝ๐๐ด๐๐ ๐ฐ๐ป}}โ$. The $\mathrm{๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐}_\mathrm{๐๐๐}$$\left(\mathrm{๐๐ธ๐๐ด}_\mathrm{๐ธ๐ฝ๐๐ด๐๐ ๐ฐ๐ป},\mathrm{๐๐ฐ๐๐บ๐},\mathrm{๐ป๐ธ๐ผ๐ธ๐}\right)$ constraint can be expressed in term of a set of reified constraints and of $K$ arithmetic constraints (i.e.,ย $\mathrm{๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐๐}$ constraints).

1. For each task $\mathrm{๐๐ฐ๐๐บ๐}\left[i\right]$ $\left(iโ\left[1,|\mathrm{๐๐ฐ๐๐บ๐}|\right]\right)$ and for each interval $\left[kยท\mathrm{๐๐ธ๐๐ด}_\mathrm{๐ธ๐ฝ๐๐ด๐๐ ๐ฐ๐ป},kยท\mathrm{๐๐ธ๐๐ด}_\mathrm{๐ธ๐ฝ๐๐ด๐๐ ๐ฐ๐ป}+\mathrm{๐๐ธ๐๐ด}_\mathrm{๐ธ๐ฝ๐๐ด๐๐ ๐ฐ๐ป}-1\right]$ $\left(kโ\left[0,K\right]\right)$ we create a 0-1 variable ${B}_{ik}$ that will be set to 1 if and only if the origin of task $\mathrm{๐๐ฐ๐๐บ๐}\left[i\right]$ is assigned within interval $\left[kยท\mathrm{๐๐ธ๐๐ด}_\mathrm{๐ธ๐ฝ๐๐ด๐๐ ๐ฐ๐ป},kยท\mathrm{๐๐ธ๐๐ด}_\mathrm{๐ธ๐ฝ๐๐ด๐๐ ๐ฐ๐ป}+\mathrm{๐๐ธ๐๐ด}_\mathrm{๐ธ๐ฝ๐๐ด๐๐ ๐ฐ๐ป}-1\right]$:

${B}_{ik}โ\mathrm{๐๐ฐ๐๐บ๐}\left[i\right].\mathrm{๐๐๐๐๐๐}โฅkยท\mathrm{๐๐ธ๐๐ด}_\mathrm{๐ธ๐ฝ๐๐ด๐๐ ๐ฐ๐ป}โง$

ย ย ย ย ย ย ย ย $\mathrm{๐๐ฐ๐๐บ๐}\left[i\right].\mathrm{๐๐๐๐๐๐}โคkยท\mathrm{๐๐ธ๐๐ด}_\mathrm{๐ธ๐ฝ๐๐ด๐๐ ๐ฐ๐ป}+\mathrm{๐๐ธ๐๐ด}_\mathrm{๐ธ๐ฝ๐๐ด๐๐ ๐ฐ๐ป}-1$

2. Finally, for each interval $\left[kยท\mathrm{๐๐ธ๐๐ด}_\mathrm{๐ธ๐ฝ๐๐ด๐๐ ๐ฐ๐ป},kยท\mathrm{๐๐ธ๐๐ด}_\mathrm{๐ธ๐ฝ๐๐ด๐๐ ๐ฐ๐ป}+\mathrm{๐๐ธ๐๐ด}_\mathrm{๐ธ๐ฝ๐๐ด๐๐ ๐ฐ๐ป}-1\right]$ $\left(kโ\left[0,K\right]\right)$, we impose the sum $\mathrm{๐๐ฐ๐๐บ๐}\left[1\right].\mathrm{๐๐๐๐๐๐}ยท{B}_{1k}+\mathrm{๐๐ฐ๐๐บ๐}\left[2\right].\mathrm{๐๐๐๐๐๐}ยท{B}_{2k}+...+\mathrm{๐๐ฐ๐๐บ๐}\left[|\mathrm{๐๐ฐ๐๐บ๐}|\right].\mathrm{๐๐๐๐๐๐}ยท{B}_{|\mathrm{๐๐ฐ๐๐บ๐}|k}$ to not exceed the maximum allowed capacity $\mathrm{๐ป๐ธ๐ผ๐ธ๐}$.

assignment dimension removed: $\mathrm{๐๐๐}_\mathrm{๐๐๐}$ย (assignment dimension corresponding to intervals is removed).

Keywords
Arc input(s)

$\mathrm{๐๐ฐ๐๐บ๐}$ $\mathrm{๐๐ฐ๐๐บ๐}$

Arc generator
$\mathrm{๐๐ ๐๐ท๐๐ถ๐}$$โฆ\mathrm{๐๐๐๐๐๐๐๐๐๐}\left(\mathrm{๐๐๐๐๐}\mathtt{1},\mathrm{๐๐๐๐๐}\mathtt{2}\right)$

Arc arity
Arc constraint(s)
$\mathrm{๐๐๐๐๐}\mathtt{1}.\mathrm{๐๐๐๐๐๐}/\mathrm{๐๐ธ๐๐ด}_\mathrm{๐ธ๐ฝ๐๐ด๐๐ ๐ฐ๐ป}=\mathrm{๐๐๐๐๐}\mathtt{2}.\mathrm{๐๐๐๐๐๐}/\mathrm{๐๐ธ๐๐ด}_\mathrm{๐ธ๐ฝ๐๐ด๐๐ ๐ฐ๐ป}$
Sets
$\begin{array}{c}\mathrm{๐ฒ๐ด๐ข๐ข}โฆ\hfill \\ \left[\begin{array}{c}\mathrm{๐๐๐๐๐๐},\hfill \\ \mathrm{๐๐๐๐๐๐๐๐๐}-\mathrm{๐๐๐}\left(\begin{array}{c}\mathrm{๐ ๐ฐ๐๐ธ๐ฐ๐ฑ๐ป๐ด๐}-\mathrm{๐๐๐๐๐๐๐๐๐๐}\left(\mathrm{๐๐๐}-\mathrm{๐๐๐๐}\right),\hfill \\ \mathrm{๐๐๐๐}\left(\mathrm{๐๐๐}-\mathrm{๐๐ฐ๐๐บ๐}.\mathrm{๐๐๐๐๐๐}\right)\right]\hfill \end{array}\right)\hfill \end{array}\right]\hfill \end{array}$

Constraint(s) on sets
$\mathrm{๐๐๐}_\mathrm{๐๐๐}$$\left(\mathrm{๐๐๐๐๐๐๐๐๐},โค,\mathrm{๐ป๐ธ๐ผ๐ธ๐}\right)$
Graph model

We use a bipartite graph where each class of vertices corresponds to the different tasks of the $\mathrm{๐๐ฐ๐๐บ๐}$ collection. There is an arc between two tasks if their origins belong to the same interval. Finally we enforce a $\mathrm{๐๐๐}_\mathrm{๐๐๐}$ constraint on each set $\mathrm{๐ฎ}$ of successors of the different vertices of the final graph. This put a restriction on the maximum value of the sum of the $\mathrm{๐๐๐๐๐๐}$ attributes of the tasks of $\mathrm{๐ฎ}$.

Partsย (A) andย (B) of Figureย 5.169.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.

Automaton

Figureย 5.169.3 depicts the automaton associated with the $\mathrm{๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐}_\mathrm{๐๐๐}$ constraint. To each item of the collection $\mathrm{๐๐ฐ๐๐บ๐}$ corresponds a signature variable ${\mathrm{๐}}_{i}$ that is equal to 1.