## 5.73. coloured_cumulative

Origin
Constraint

$\mathrm{๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐๐๐๐๐}\left(\mathrm{๐๐ฐ๐๐บ๐},\mathrm{๐ป๐ธ๐ผ๐ธ๐}\right)$

Synonym

$\mathrm{๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐๐๐๐๐}$.

Arguments
 $\mathrm{๐๐ฐ๐๐บ๐}$ $\mathrm{๐๐๐๐๐๐๐๐๐๐}\left(\begin{array}{c}\mathrm{๐๐๐๐๐๐}-\mathrm{๐๐๐๐},\hfill \\ \mathrm{๐๐๐๐๐๐๐๐}-\mathrm{๐๐๐๐},\hfill \\ \mathrm{๐๐๐}-\mathrm{๐๐๐๐},\hfill \\ \mathrm{๐๐๐๐๐๐}-\mathrm{๐๐๐๐}\hfill \end{array}\right)$ $\mathrm{๐ป๐ธ๐ผ๐ธ๐}$ $\mathrm{๐๐๐}$
Restrictions
 $\mathrm{๐๐๐๐๐๐๐}_\mathrm{๐๐}_\mathrm{๐๐๐๐๐}$$\left(2,\mathrm{๐๐ฐ๐๐บ๐},\left[\mathrm{๐๐๐๐๐๐},\mathrm{๐๐๐๐๐๐๐๐},\mathrm{๐๐๐}\right]\right)$ $\mathrm{๐๐๐๐๐๐๐๐}$$\left(\mathrm{๐๐ฐ๐๐บ๐},\mathrm{๐๐๐๐๐๐}\right)$ $\mathrm{๐๐ฐ๐๐บ๐}.\mathrm{๐๐๐๐๐๐๐๐}โฅ0$ $\mathrm{๐๐ฐ๐๐บ๐}.\mathrm{๐๐๐๐๐๐}โค\mathrm{๐๐ฐ๐๐บ๐}.\mathrm{๐๐๐}$ $\mathrm{๐ป๐ธ๐ผ๐ธ๐}โฅ0$
Purpose

Consider the set $\mathrm{๐ฏ}$ of tasks described by the $\mathrm{๐๐ฐ๐๐บ๐}$ collection. The $\mathrm{๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐๐๐๐๐}$ constraint forces that, at each point in time, the number of distinct colours of the set of tasks that overlap that point, does not exceed a given limit. A task overlaps a point $i$ if and only if (1)ย its origin is less than or equal to $i$, and (2)ย its end is strictly greater than $i$. For each task of $\mathrm{๐ฏ}$ it also imposes the constraint $\mathrm{๐๐๐๐๐๐}+\mathrm{๐๐๐๐๐๐๐๐}=\mathrm{๐๐๐}$.

Example
$\left(\begin{array}{c}โฉ\begin{array}{cccc}\mathrm{๐๐๐๐๐๐}-1\hfill & \mathrm{๐๐๐๐๐๐๐๐}-2\hfill & \mathrm{๐๐๐}-3\hfill & \mathrm{๐๐๐๐๐๐}-1,\hfill \\ \mathrm{๐๐๐๐๐๐}-2\hfill & \mathrm{๐๐๐๐๐๐๐๐}-9\hfill & \mathrm{๐๐๐}-11\hfill & \mathrm{๐๐๐๐๐๐}-2,\hfill \\ \mathrm{๐๐๐๐๐๐}-3\hfill & \mathrm{๐๐๐๐๐๐๐๐}-10\hfill & \mathrm{๐๐๐}-13\hfill & \mathrm{๐๐๐๐๐๐}-3,\hfill \\ \mathrm{๐๐๐๐๐๐}-6\hfill & \mathrm{๐๐๐๐๐๐๐๐}-6\hfill & \mathrm{๐๐๐}-12\hfill & \mathrm{๐๐๐๐๐๐}-2,\hfill \\ \mathrm{๐๐๐๐๐๐}-7\hfill & \mathrm{๐๐๐๐๐๐๐๐}-2\hfill & \mathrm{๐๐๐}-9\hfill & \mathrm{๐๐๐๐๐๐}-3\hfill \end{array}โช,2\hfill \end{array}\right)$

Figureย 5.73.1 shows the solution associated with the example. Each rectangle of the figure corresponds to a task of the $\mathrm{๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐๐๐๐๐}$ constraint. Tasks that have their colour attribute set to 1, 2 and 3 are respectively coloured in yellow, blue and pink. The $\mathrm{๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐๐๐๐๐}$ constraint holds since at each point in time we do not have more than $\mathrm{๐ป๐ธ๐ผ๐ธ๐}=2$ distinct colours.

Typical
 $|\mathrm{๐๐ฐ๐๐บ๐}|>1$ $\mathrm{๐๐๐๐๐}$$\left(\mathrm{๐๐ฐ๐๐บ๐}.\mathrm{๐๐๐๐๐๐}\right)>1$ $\mathrm{๐๐๐๐๐}$$\left(\mathrm{๐๐ฐ๐๐บ๐}.\mathrm{๐๐๐๐๐๐๐๐}\right)>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{๐๐๐๐๐๐}$ and $\mathrm{๐๐๐}$ attributes of all items of $\mathrm{๐๐ฐ๐๐บ๐}$.

• All occurrences of two distinct values of $\mathrm{๐๐ฐ๐๐บ๐}.\mathrm{๐๐๐๐๐๐}$ can be swapped; all occurrences of a value of $\mathrm{๐๐ฐ๐๐บ๐}.\mathrm{๐๐๐๐๐๐}$ can be renamed to any unused value.

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

Arg. properties

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

Usage

Useful for scheduling problems where a machine can only proceed in parallel a maximum number of tasks of distinct type. This condition cannot be modelled by the classical $\mathrm{๐๐๐๐๐๐๐๐๐๐}$ constraint. Also useful for coloured bin packing problems (i.e., $\mathrm{๐๐๐๐๐๐๐๐}=1$) where each item has a colour and no bin contains items with more than $\mathrm{๐ป๐ธ๐ผ๐ธ๐}$ distinct coloursย [DawandeKalagnanamSethuraman98], [GarganiRefalo07], [HeinzSchlechteStephanWinkler12].

Reformulation

The $\mathrm{๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐๐๐๐๐}$ constraint can be expressed in term of a set of reified constraints and of $|\mathrm{๐๐ฐ๐๐บ๐}|$ $\mathrm{๐๐๐๐๐๐}$ constraints:

1. For each pair of tasks $\mathrm{๐๐ฐ๐๐บ๐}\left[i\right],\mathrm{๐๐ฐ๐๐บ๐}\left[j\right]$ $\left(i,jโ\left[1,|\mathrm{๐๐ฐ๐๐บ๐}|\right]\right)$ of the $\mathrm{๐๐ฐ๐๐บ๐}$ collection we create a variable ${C}_{ij}$ which is set to the colour of task $\mathrm{๐๐ฐ๐๐บ๐}\left[j\right]$ if task $\mathrm{๐๐ฐ๐๐บ๐}\left[j\right]$ overlaps the origin attribute of task $\mathrm{๐๐ฐ๐๐บ๐}\left[i\right]$, and to the colour of task $\mathrm{๐๐ฐ๐๐บ๐}\left[i\right]$ otherwise:

• If $i=j$:

• ${C}_{ij}=\mathrm{๐๐ฐ๐๐บ๐}\left[i\right].\mathrm{๐๐๐๐๐๐}$.

• If :

• ${C}_{ij}=\mathrm{๐๐ฐ๐๐บ๐}\left[i\right].\mathrm{๐๐๐๐๐๐}โจ{C}_{ij}=\mathrm{๐๐ฐ๐๐บ๐}\left[j\right].\mathrm{๐๐๐๐๐๐}$.

• $\left(\left(\mathrm{๐๐ฐ๐๐บ๐}\left[j\right].\mathrm{๐๐๐๐๐๐}โค\mathrm{๐๐ฐ๐๐บ๐}\left[i\right].\mathrm{๐๐๐๐๐๐}โง$

ย ย ย $\mathrm{๐๐ฐ๐๐บ๐}\left[j\right].\mathrm{๐๐๐}>\mathrm{๐๐ฐ๐๐บ๐}\left[i\right].\mathrm{๐๐๐๐๐๐}\right)โง\left({C}_{ij}=\mathrm{๐๐ฐ๐๐บ๐}\left[j\right].\mathrm{๐๐๐๐๐๐}\right)\right)โจ$

$\left(\left(\mathrm{๐๐ฐ๐๐บ๐}\left[j\right].\mathrm{๐๐๐๐๐๐}>\mathrm{๐๐ฐ๐๐บ๐}\left[i\right].\mathrm{๐๐๐๐๐๐}โจ$

ย ย ย $\mathrm{๐๐ฐ๐๐บ๐}\left[j\right].\mathrm{๐๐๐}โค\mathrm{๐๐ฐ๐๐บ๐}\left[i\right].\mathrm{๐๐๐๐๐๐}\right)โง\left({C}_{ij}=\mathrm{๐๐ฐ๐๐บ๐}\left[i\right].\mathrm{๐๐๐๐๐๐}\right)\right)$

2. For each task $\mathrm{๐๐ฐ๐๐บ๐}\left[i\right]$ $\left(iโ\left[1,|\mathrm{๐๐ฐ๐๐บ๐}|\right]\right)$ we create a variable ${N}_{i}$ which gives the number of distinct colours associated with the tasks that overlap the origin of task $\mathrm{๐๐ฐ๐๐บ๐}\left[i\right]$ ($\mathrm{๐๐ฐ๐๐บ๐}\left[i\right]$ overlaps its own origin) and we impose ${N}_{i}$ to not exceed the maximum number of distinct colours $\mathrm{๐ป๐ธ๐ผ๐ธ๐}$ allowed at each instant:

specialisation: $\mathrm{๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐}$ย (a colour is assigned to each collection of tasks of constraint $\mathrm{๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐}$ and a limit of one single colour is enforced).

Keywords
Arc input(s)

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

Arc generator
$\mathrm{๐๐ธ๐ฟ๐น}$$โฆ\mathrm{๐๐๐๐๐๐๐๐๐๐}\left(\mathrm{๐๐๐๐๐}\right)$

Arc arity
Arc constraint(s)
$\mathrm{๐๐๐๐๐}.\mathrm{๐๐๐๐๐๐}+\mathrm{๐๐๐๐๐}.\mathrm{๐๐๐๐๐๐๐๐}=\mathrm{๐๐๐๐๐}.\mathrm{๐๐๐}$
Graph property(ies)
$\mathrm{๐๐๐๐}$$=|\mathrm{๐๐ฐ๐๐บ๐}|$

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{๐๐๐๐๐๐๐๐}>0$ $โข\mathrm{๐๐๐๐๐}\mathtt{2}.\mathrm{๐๐๐๐๐๐}โค\mathrm{๐๐๐๐๐}\mathtt{1}.\mathrm{๐๐๐๐๐๐}$ $โข\mathrm{๐๐๐๐๐}\mathtt{1}.\mathrm{๐๐๐๐๐๐}<\mathrm{๐๐๐๐๐}\mathtt{2}.\mathrm{๐๐๐}$
Graph class
 $โข$$\mathrm{๐ฐ๐ฒ๐๐ฒ๐ป๐ธ๐ฒ}$ $โข$$\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{๐๐๐๐๐๐๐}$$\left(\mathrm{๐๐๐๐๐๐๐๐๐},โค,\mathrm{๐ป๐ธ๐ผ๐ธ๐}\right)$
Graph model

Same as $\mathrm{๐๐๐๐๐๐๐๐๐๐}$, except that we use another constraint for computing the resource consumption at each time point.

Partsย (A) andย (B) of Figureย 5.73.2 respectively show the initial and final graph associated with the second graph constraint of the Example slot. On the one hand, each source vertex of the final graph can be interpreted as a time point. On the other hand the successors of a source vertex correspond to those tasks that overlap that time point. The $\mathrm{๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐๐๐๐๐}$ constraint holds since for each successor set $\mathrm{๐ฎ}$ of the final graph the number of distinct colours of the tasks in $\mathrm{๐ฎ}$ does not exceed the $\mathrm{๐ป๐ธ๐ผ๐ธ๐}$ 2.

Signature

Since $\mathrm{๐๐ฐ๐๐บ๐}$ is the maximum number of vertices of the final graph of the first graph constraint we can rewrite $\mathrm{๐๐๐๐}$ $=$ $|\mathrm{๐๐ฐ๐๐บ๐}|$ to $\mathrm{๐๐๐๐}$ $โฅ$ $|\mathrm{๐๐ฐ๐๐บ๐}|$. This leads to simplify $\underset{ฬฒ}{\stackrel{ยฏ}{\mathrm{๐๐๐๐}}}$ to $\stackrel{ยฏ}{\mathrm{๐๐๐๐}}$.