## 5.98. 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{๐๐๐๐๐๐๐๐}โฅ0$ $\mathrm{๐๐ฐ๐๐บ๐}.\mathrm{๐๐๐๐๐๐}โค\mathrm{๐๐ฐ๐๐บ๐}.\mathrm{๐๐๐}$ $\mathrm{๐๐ฐ๐๐บ๐}.\mathrm{๐๐๐๐๐๐}โฅ1$ $\mathrm{๐ป๐ธ๐ผ๐ธ๐}โฅ0$
Purpose

Consider a set $\mathrm{๐ฏ}$ of tasks described by the $\mathrm{๐๐ฐ๐๐บ๐}$ collection. The $\mathrm{๐๐๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐๐}$ constraint forces 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 $\mathrm{๐ฏ}$ 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.98.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 $โฅ0$.

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

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

Arg. properties

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

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{๐๐ฐ๐๐บ๐}|}โคl$:

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 ${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 :

• ${H}_{ij}=\mathrm{๐๐ฐ๐๐บ๐}\left[j\right].\mathrm{๐๐๐๐๐๐}โจ{H}_{ij}=1$.

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

ย ย ย $\mathrm{๐๐ฐ๐๐บ๐}\left[j\right].\mathrm{๐๐๐}>\mathrm{๐๐ฐ๐๐บ๐}\left[i\right].\mathrm{๐๐๐๐๐๐}\right)โง\left({H}_{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({H}_{ij}=1\right)\right)$

2. For each task $\mathrm{๐๐ฐ๐๐บ๐}\left[i\right]$ $\left(iโ\left[1,|\mathrm{๐๐ฐ๐๐บ๐}|\right]\right)$ we impose a constraint of the form ${H}_{i1}ยท{H}_{i2}ยทโฏยท{H}_{i|\mathrm{๐๐ฐ๐๐บ๐}|}โค\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{๐๐๐๐๐๐}โค\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{๐๐๐๐๐๐๐๐๐},โค,\mathrm{๐ป๐ธ๐ผ๐ธ๐}\right)$
Graph model

Partsย (A) andย (B) of Figureย 5.98.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 product of the heights of the tasks in $\mathrm{๐ฎ}$ 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{๐๐๐๐}$ $โฅ$ $|\mathrm{๐๐ฐ๐๐บ๐}|$. This leads to simplify $\underset{ฬฒ}{\stackrel{ยฏ}{\mathrm{๐๐๐๐}}}$ to $\stackrel{ยฏ}{\mathrm{๐๐๐๐}}$.