## 5.82. cumulative

Origin
Constraint

$\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{๐๐ฐ๐๐บ๐}.\mathrm{๐๐๐๐๐๐}โฅ0$ $\mathrm{๐ป๐ธ๐ผ๐ธ๐}โฅ0$
Purpose

Cumulative scheduling constraint or scheduling under resource constraints. Consider a set $\mathrm{๐ฏ}$ of tasks described by the $\mathrm{๐๐ฐ๐๐บ๐}$ collection. The $\mathrm{๐๐๐๐๐๐๐๐๐๐}$ constraint enforces that at each point in time, the cumulated height 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}โช,8\hfill \end{array}\right)$

Figureย 5.82.1 shows the cumulated profile associated with the example. To each task of the $\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 resource consumption of the task. The $\mathrm{๐๐๐๐๐๐๐๐๐๐}$ constraint holds since at each point in time we do not have a cumulated resource consumption strictly greater than the upper limit 8 enforced by the last argument of the $\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{๐๐๐๐๐๐}>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.

Remark

In the original $\mathrm{๐๐๐๐๐๐๐๐๐๐}$ constraint of CHIP the $\mathrm{๐ป๐ธ๐ผ๐ธ๐}$ parameter was a domain variable corresponding to the maximum peak of the resource consumption profile. Given a fixed time frame, this variable could be used as a cost in order to directly minimise the maximum resource consumption peak.

Some systems like Ilogย CPย Optimizer also assume that a zero -duration task overlaps a point $i$ if and only if (1)ย its origin is less than or equal to $i$, and (2)ย its end is greater than or equal to $i$. Under this definition, the height of a zero -duration task is also taken into account in the resource consumption profile.

Note that the concept of cumulative is different from the concept of rectangles non -overlapping even if, most of the time, each task of a ground solution of a $\mathrm{๐๐๐๐๐๐๐๐๐๐}$ constraint is simply drawn as a single rectangle. As illustrated by Figureย 5.100.5, this is in fact not always possible (i.e.,ย some rectangles may need to be broken apart). In fact the $\mathrm{๐๐๐๐๐๐๐๐๐๐}$ constraint is only a necessary condition for rectangles non -overlapping (see Figureย 5.100.4 and the corresponding explanation in the Algorithm slot of the $\mathrm{๐๐๐๐๐}$ constraint).

Algorithm

The first filtering algorithms were related to the notion of compulsory part of a taskย [Lahrichi82]. They compute a cumulated resource profile of all the compulsory parts of the tasks and prune the origins of the tasks with respect to this profile in order to not exceed the resource capacity. These methods are sometimes called time tabling. Even if these methods are quite local, i.e.,ย a task has a non -empty compulsory part only when the difference between its latest start and its earliest start is strictly less than its duration, it scales well and is therefore widely used. Later on, more global algorithmsEven if these more global algorithms usually can prune more early in the search tree, these algorithms do not catch all deductions derived from the cumulated resource profile of compulsory parts. based on the resource consumption of the tasks on specific intervals were introducedย [ErschlerLopez90], [CaseauLaburthe96b], [Lock96]. A popular variant, called edge finding, considers only specific intervalsย [MercierVanHentenryck08]. An efficient implementation of edge finding in $O\left(knlogn\right)$, where $k$ is the number of distinct task heights and $n$ is the number of tasks, based on a specific data structure, so called a cumulative $\mathrm{ฮฆ}$ -treeย [Vilim09a], is provided inย [Vilim09b]. A $O\left({n}^{2}logn\right)$ filtering algorithm based on tasks that can not be the earliest (or not be the latest) is described inย [SchuttWolf10].

Within the context of linear programming, the referenceย [HookerYan02] provides a relaxation of the $\mathrm{๐๐๐๐๐๐๐๐๐๐}$ constraint.

A necessary condition for the $\mathrm{๐๐๐๐๐๐๐๐๐๐}$ constraint is obtained by stating a $\mathrm{๐๐๐๐๐๐๐๐๐๐๐}$ constraint on a subset of tasks $\mathrm{๐ฏ}$ such that, for each pair of tasks of $\mathrm{๐ฏ}$, the sum of the two corresponding minimum heights is strictly greater than $\mathrm{๐ป๐ธ๐ผ๐ธ๐}$. This can be done by applying the following procedure:

• Let $h$ be the smallest minimum height strictly greater than $โ\frac{\mathrm{๐ป๐ธ๐ผ๐ธ๐}}{2}โ$ of the tasks of the $\mathrm{๐๐๐๐๐๐๐๐๐๐}$ constraint. If no such task exists then the procedure is stopped without stating any $\mathrm{๐๐๐๐๐๐๐๐๐๐๐}$ constraint.

• Let ${\mathrm{๐ฏ}}_{h}$ denote the set of tasks of the $\mathrm{๐๐๐๐๐๐๐๐๐๐}$ constraint for which the minimum height is greater than or equal to $h$. By construction, the tasks of ${\mathrm{๐ฏ}}_{h}$ cannot overlap. But we can eventually add one more task as shown by the next step.

• When it exists, we can add one task that does not belong to ${\mathrm{๐ฏ}}_{h}$ and such that its minimum height is strictly greater than $\mathrm{๐ป๐ธ๐ผ๐ธ๐}-h$. Again, by construction, this task cannot overlap all the tasks of ${\mathrm{๐ฏ}}_{h}$.

When the tasks are involved in several $\mathrm{๐๐๐๐๐๐๐๐๐๐}$ constraints more sophisticated methods are available for extracting $\mathrm{๐๐๐๐๐๐๐๐๐๐๐}$ constraintsย [BaptisteLePape00], [BaptisteDemassey04].

In the context where, both the duration and height of all the tasks are fixed, [BeldiceanuCarlssonPoder08] provides two kinds of additional filtering algorithms that are specially useful when the slack $\mathrm{ฯ}$ (i.e.,ย the difference between the available space and the sum of the surfaces of the tasks) is very small:

• The first one introduces bounds for the so called cumulative longest hole problem. Given an integer $\mathrm{ฯต}$ that does not exceed the resource limit, and a subset of tasks ${\mathrm{๐ฏ}}^{\text{'}}$ for which the resource consumption is a most $\mathrm{ฯต}$, the cumulative longest hole problem is to find the largest integer ${\mathrm{๐๐๐๐ฅ}}_{\mathrm{ฯ}}^{\mathrm{ฯต}}\left({\mathrm{๐ฏ}}^{\text{'}}\right)$ such that there is a cumulative placement of maximum height $\mathrm{ฯต}$ involving a subset of tasks of ${\mathrm{๐ฏ}}^{\text{'}}$ where, on one interval $\left[i,i+{\mathrm{๐๐๐๐ฅ}}_{\mathrm{ฯ}}^{\mathrm{ฯต}}\left({\mathrm{๐ฏ}}^{\text{'}}\right)-1\right]$ of the cumulative profile, the area of the empty space does not exceed $\mathrm{ฯ}$.

• The second one used dynamic programming for filtering so called balancing knapsack constraints. When the slack is 0, such constraints express the fact that the total height of tasks ending at instant $i$ must equal the total height of tasks starting at instant $i$. Such constraints can be generalized to non -zero slack.

Systems

assignment dimension added: $\mathrm{๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐๐๐๐๐๐}$ย (sum of $\mathrm{๐๐๐๐}$ $\mathrm{๐๐๐๐๐๐๐}$ replaced by number of distinct $\mathrm{๐๐๐๐๐๐๐}$, assignment dimension added), $\mathrm{๐๐๐๐๐๐๐๐๐๐๐}$ย (negative $\mathrm{๐๐๐๐๐๐๐}$ allowed and assignment dimension added).

common keyword: $\mathrm{๐๐๐๐๐๐๐๐}$ย (scheduling constraint), $\mathrm{๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐๐๐๐๐}$ย (resource constraint, sum of $\mathrm{๐๐๐๐}$ $\mathrm{๐๐๐๐๐๐๐}$ replaced by number of distinct values), $\mathrm{๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐๐๐๐๐๐}$ย (resource constraint), $\mathrm{๐๐๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐ก}$ย (resource constraint, $\mathrm{๐๐๐๐}$ defined by a set of $\mathrm{๐๐๐๐๐๐}$), $\mathrm{๐๐๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐๐}$ย (resource constraint, sum of $\mathrm{๐๐๐๐}$ $\mathrm{๐๐๐๐๐๐๐}$ replaced by product of $\mathrm{๐๐๐๐}$ $\mathrm{๐๐๐๐๐๐๐}$), ย (resource constraint, a $\mathrm{๐๐๐๐๐๐๐๐๐๐}$ constraint for each set of $\mathrm{๐๐๐๐๐}$ having a priority less than or equal to a given threshold).

generalisation: ย ($\mathrm{๐๐๐๐}$ replaced by $\mathrm{๐๐๐๐๐๐๐๐๐}$ with a $\mathrm{๐๐๐๐๐๐}$).

implied by: $\mathrm{๐๐๐๐๐}$ย ($\mathrm{๐๐๐๐๐๐๐๐๐๐}$ is a neccessary condition for each dimension of the $\mathrm{๐๐๐๐๐}$ constraint).

related: $\mathrm{๐๐๐ก}_\mathrm{๐๐๐๐๐}_\mathrm{๐๐๐๐}$, $\mathrm{๐๐๐ก}_\mathrm{๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐}$ย (lexicographic ordering on the origins of $\mathrm{๐๐๐๐๐}$, $\mathrm{๐๐๐๐๐๐๐๐๐๐}$, $...$), $\mathrm{๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐๐๐๐๐๐ข}$ย (controlling the shape of the cumulative profile for breaking symmetry).

specialisation: $\mathrm{๐๐๐๐๐๐}$ย ($\mathrm{๐๐๐๐}$ replaced by $\mathrm{๐๐๐๐๐๐๐๐}$), $\mathrm{๐๐๐}_\mathrm{๐๐๐๐๐๐๐}$ย (all $\mathrm{๐๐๐๐๐}$ have a $\mathrm{๐๐๐๐๐๐๐๐}$ of 1 and a fixed $\mathrm{๐๐๐๐๐๐}$), $\mathrm{๐๐๐๐๐๐๐๐๐๐๐}$ย (all $\mathrm{๐๐๐๐๐}$ have a $\mathrm{๐๐๐๐๐๐}$ of 1).

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

The first graph constraint enforces for each task the link between its origin, its duration and its end. The second graph constraint makes sure, for each time point $t$ corresponding to the start of a task, that the cumulated heights of the tasks that overlap $t$ does not exceed the limit of the resource.

Partsย (A) andย (B) of Figureย 5.82.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{๐๐๐๐๐๐๐๐๐๐}$ constraint holds since for each successor set $\mathrm{๐ฎ}$ of the final graph the sum of the heights of the tasks in $\mathrm{๐ฎ}$ does not exceed the limit $\mathrm{๐ป๐ธ๐ผ๐ธ๐}=8$.

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{๐๐๐๐}}$.

Automaton

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