## 5.84. cumulative_product

Origin
Constraint

$\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}_\mathrm{𝚙𝚛𝚘𝚍𝚞𝚌𝚝}\left(\mathrm{𝚃𝙰𝚂𝙺𝚂},\mathrm{𝙻𝙸𝙼𝙸𝚃}\right)$

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{𝚃𝙰𝚂𝙺𝚂}.\mathrm{𝚑𝚎𝚒𝚐𝚑𝚝}\ge 1$ $\mathrm{𝙻𝙸𝙼𝙸𝚃}\ge 0$
Purpose

Consider a set $𝒯$ of tasks described by the $\mathrm{𝚃𝙰𝚂𝙺𝚂}$ collection. The $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}_\mathrm{𝚙𝚛𝚘𝚍𝚞𝚌𝚝}$ constraint enforces that at each point in time, the product of the heights 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$. It also imposes for each task of $𝒯$ the constraint $\mathrm{𝚘𝚛𝚒𝚐𝚒𝚗}+\mathrm{𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗}=\mathrm{𝚎𝚗𝚍}$.

Example
$\left(\begin{array}{c}〈\begin{array}{cccc}\mathrm{𝚘𝚛𝚒𝚐𝚒𝚗}-1\hfill & \mathrm{𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗}-3\hfill & \mathrm{𝚎𝚗𝚍}-4\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{𝚑𝚎𝚒𝚐𝚑𝚝}-1,\hfill \\ \mathrm{𝚘𝚛𝚒𝚐𝚒𝚗}-6\hfill & \mathrm{𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗}-6\hfill & \mathrm{𝚎𝚗𝚍}-12\hfill & \mathrm{𝚑𝚎𝚒𝚐𝚑𝚝}-1,\hfill \\ \mathrm{𝚘𝚛𝚒𝚐𝚒𝚗}-7\hfill & \mathrm{𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗}-2\hfill & \mathrm{𝚎𝚗𝚍}-9\hfill & \mathrm{𝚑𝚎𝚒𝚐𝚑𝚝}-3\hfill \end{array}〉,6\hfill \end{array}\right)$

Figure 5.84.1 shows the solution associated with the example. To each task of the $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}_\mathrm{𝚙𝚛𝚘𝚍𝚞𝚌𝚝}$ constraint corresponds a set of rectangles coloured with the same colour: the sum of the lengths of the rectangles corresponds to the duration of the task, while the height of the rectangles (i.e., all the rectangles associated with a task have the same height) corresponds to the height of the task. The profile corresponding to the product of the heights of the tasks that overlap a given point is depicted by a thick red line. The $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}_\mathrm{𝚙𝚛𝚘𝚍𝚞𝚌𝚝}$ constraint holds since at each point in time the product of the heights of the tasks that overlap that point is not strictly greater than the upper limit 6 enforced by the last argument of the $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}_\mathrm{𝚙𝚛𝚘𝚍𝚞𝚌𝚝}$ constraint.

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{𝚍𝚞𝚛𝚊𝚝𝚒𝚘𝚗}>0$ $\mathrm{𝙻𝙸𝙼𝙸𝚃}<$$\mathrm{𝚙𝚛𝚘𝚍}$$\left(\mathrm{𝚃𝙰𝚂𝙺𝚂}.\mathrm{𝚑𝚎𝚒𝚐𝚑𝚝}\right)$
Symmetries
• Items of $\mathrm{𝚃𝙰𝚂𝙺𝚂}$ are permutable.

• $\mathrm{𝚃𝙰𝚂𝙺𝚂}.\mathrm{𝚑𝚎𝚒𝚐𝚑𝚝}$ can be decreased to any value $\ge 0$.

• One and the same constant can be added to the $\mathrm{𝚘𝚛𝚒𝚐𝚒𝚗}$ and $\mathrm{𝚎𝚗𝚍}$ attributes of all items of $\mathrm{𝚃𝙰𝚂𝙺𝚂}$.

• $\mathrm{𝙻𝙸𝙼𝙸𝚃}$ can be increased.

Reformulation

The $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}_\mathrm{𝚙𝚛𝚘𝚍𝚞𝚌𝚝}$ constraint can be expressed in term of a set of reified constraints and of $|\mathrm{𝚃𝙰𝚂𝙺𝚂}|$ constraints of the form ${h}_{1}·{h}_{2}·...·{h}_{|\mathrm{𝚃𝙰𝚂𝙺𝚂}|}\le l$:

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 ${H}_{ij}$ which is set to the height of task $\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[j\right]$ if task $\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[j\right]$ overlaps the origin attribute of task $\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[i\right]$, and to 1 otherwise:

• If $i=j$:

• ${H}_{ij}=\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[i\right].\mathrm{𝚑𝚎𝚒𝚐𝚑𝚝}$.

• If $i\ne j$:

• ${H}_{ij}=\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[j\right].\mathrm{𝚑𝚎𝚒𝚐𝚑𝚝}\vee {H}_{ij}=1$.

• $\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({H}_{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({H}_{ij}=1\right)\right)$

2. For each task $\mathrm{𝚃𝙰𝚂𝙺𝚂}\left[i\right]$ $\left(i\in \left[1,|\mathrm{𝚃𝙰𝚂𝙺𝚂}|\right]\right)$ we impose a constraint of the form ${H}_{i1}·{H}_{i2}·...·{H}_{i|\mathrm{𝚃𝙰𝚂𝙺𝚂}|}\le \mathrm{𝙻𝙸𝙼𝙸𝚃}$.

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{𝚙𝚛𝚘𝚍𝚞𝚌𝚝}_\mathrm{𝚌𝚝𝚛}$$\left(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜},\le ,\mathrm{𝙻𝙸𝙼𝙸𝚃}\right)$
Graph model

Parts (A) and (B) of Figure 5.84.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 product of the heights of the tasks in $𝒮$ does not exceed the limit $\mathrm{𝙻𝙸𝙼𝙸𝚃}=6$.

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{𝐍𝐀𝐑𝐂}}$.