## 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{𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗}\ge 0$ $\mathrm{𝚃𝙰𝚂𝙺𝚂}.\mathrm{𝚘𝚛𝚒𝚐𝚒𝚗}\le \mathrm{𝚃𝙰𝚂𝙺𝚂}.\mathrm{𝚎𝚗𝚍}$ $\mathrm{𝙻𝙸𝙼𝙸𝚃}\ge 0$
Purpose

Consider the set $𝒯$ 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 $𝒯$ 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\in \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 $i\ne j$:

• ${C}_{ij}=\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[i\right].\mathrm{𝚌𝚘𝚕𝚘𝚞𝚛}\vee {C}_{ij}=\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[j\right].\mathrm{𝚌𝚘𝚕𝚘𝚞𝚛}$.

• $\left(\left(\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[j\right].\mathrm{𝚘𝚛𝚒𝚐𝚒𝚗}\le \mathrm{𝚃𝙰𝚂𝙺𝚂}\left[i\right].\mathrm{𝚘𝚛𝚒𝚐𝚒𝚗}\wedge$

$\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[j\right].\mathrm{𝚎𝚗𝚍}>\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[i\right].\mathrm{𝚘𝚛𝚒𝚐𝚒𝚗}\right)\wedge \left({C}_{ij}=\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[j\right].\mathrm{𝚌𝚘𝚕𝚘𝚞𝚛}\right)\right)\vee$

$\left(\left(\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[j\right].\mathrm{𝚘𝚛𝚒𝚐𝚒𝚗}>\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[i\right].\mathrm{𝚘𝚛𝚒𝚐𝚒𝚗}\vee$

$\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[j\right].\mathrm{𝚎𝚗𝚍}\le \mathrm{𝚃𝙰𝚂𝙺𝚂}\left[i\right].\mathrm{𝚘𝚛𝚒𝚐𝚒𝚗}\right)\wedge \left({C}_{ij}=\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[i\right].\mathrm{𝚌𝚘𝚕𝚘𝚞𝚛}\right)\right)$

2. For each task $\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[i\right]$ $\left(i\in \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{𝚘𝚛𝚒𝚐𝚒𝚗}\le \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{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜},\le ,\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 $𝒮$ of the final graph the number of distinct colours of the tasks in $𝒮$ 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{𝐍𝐀𝐑𝐂}$ $\ge$ $|\mathrm{𝚃𝙰𝚂𝙺𝚂}|$. This leads to simplify $\underline{\overline{\mathrm{𝐍𝐀𝐑𝐂}}}$ to $\overline{\mathrm{𝐍𝐀𝐑𝐂}}$.