## 5.97. cumulative_convex

Origin
Constraint

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

Type
 $\mathrm{๐ฟ๐พ๐ธ๐ฝ๐๐}$ $\mathrm{๐๐๐๐๐๐๐๐๐๐}\left(\mathrm{๐๐๐}-\mathrm{๐๐๐๐}\right)$
Arguments
 $\mathrm{๐๐ฐ๐๐บ๐}$ $\mathrm{๐๐๐๐๐๐๐๐๐๐}\left(\mathrm{๐๐๐๐๐๐}-\mathrm{๐ฟ๐พ๐ธ๐ฝ๐๐},\mathrm{๐๐๐๐๐๐}-\mathrm{๐๐๐๐}\right)$ $\mathrm{๐ป๐ธ๐ผ๐ธ๐}$ $\mathrm{๐๐๐}$
Restrictions
 $\mathrm{๐๐๐๐๐๐๐๐}$$\left(\mathrm{๐ฟ๐พ๐ธ๐ฝ๐๐},\mathrm{๐๐๐}\right)$ $|\mathrm{๐ฟ๐พ๐ธ๐ฝ๐๐}|>0$ $\mathrm{๐๐๐๐๐๐๐๐}$$\left(\mathrm{๐๐ฐ๐๐บ๐},\left[\mathrm{๐๐๐๐๐๐},\mathrm{๐๐๐๐๐๐}\right]\right)$ $\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 where each task is defined by:

• A set of distinct points depicting the time interval where the task is actually running: the smallest and largest coordinates of these points respectively give the first and last instant of that time interval.

• A height that depicts the resource consumption used by the task from its first instant to its last instant.

The $\mathrm{๐๐๐๐๐๐๐๐๐๐}_\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$.

Example
$\left(\begin{array}{c}โฉ\begin{array}{cc}\mathrm{๐๐๐๐๐๐}-โฉ2,1,5โช\hfill & \mathrm{๐๐๐๐๐๐}-1,\hfill \\ \mathrm{๐๐๐๐๐๐}-โฉ4,5,7โช\hfill & \mathrm{๐๐๐๐๐๐}-2,\hfill \\ \mathrm{๐๐๐๐๐๐}-โฉ14,13,9,11,10โช\hfill & \mathrm{๐๐๐๐๐๐}-2\hfill \end{array}โช,3\hfill \end{array}\right)$

Figureย 5.97.1 shows the cumulated profile associated with the example. To each set of points defining a task corresponds a rectangle. The height of each rectangle represents the resource consumption of the associated task. The $\mathrm{๐๐๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐ก}$ constraint holds since at each point in time we do not have a cumulated resource consumption strictly greater than the upper limit 3 enforced by the last argument of the $\mathrm{๐๐๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐ก}$ constraint.

Typical
 $|\mathrm{๐๐ฐ๐๐บ๐}|>1$ $\mathrm{๐๐ฐ๐๐บ๐}.\mathrm{๐๐๐๐๐๐}>0$ $\mathrm{๐ป๐ธ๐ผ๐ธ๐}<$$\mathrm{๐๐๐}$$\left(\mathrm{๐๐ฐ๐๐บ๐}.\mathrm{๐๐๐๐๐๐}\right)$
Symmetries
• Items of $\mathrm{๐๐ฐ๐๐บ๐}$ are permutable.

• Items of $\mathrm{๐๐ฐ๐๐บ๐}.\mathrm{๐๐๐๐๐๐}$ are permutable.

• $\mathrm{๐๐ฐ๐๐บ๐}.\mathrm{๐๐๐๐๐๐}$ can be decreased to any value $โฅ0$.

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

Arg. properties

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

Usage

A natural use of the $\mathrm{๐๐๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐ก}$ constraint corresponds to problems where a task is defined as the convex hull of a set of distinct points ${P}_{1},โฏ,{P}_{n}$ that are not initially fixed. Note that, by explicitly introducing a start $S$ and an end $E$ variables, and by using a $\mathrm{๐๐๐๐๐๐๐}$$\left(S,โฉ\mathrm{๐๐๐}-{P}_{1},โฏ,\mathrm{๐๐๐}-{P}_{n}โช\right)$ and a $\mathrm{๐๐๐ก๐๐๐๐}$$\left(E,โฉ\mathrm{๐๐๐}-{P}_{1},โฏ,\mathrm{๐๐๐}-{P}_{n}โช\right)$ constraints, one could replace the $\mathrm{๐๐๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐ก}$ constraint by a $\mathrm{๐๐๐๐๐๐๐๐๐๐}$ constraint. However this hinders propagation.

As a concrete example of use of the $\mathrm{๐๐๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐ก}$ constraint we present a constraint model for a well-known pattern-sequencing problemย [FinkVoss99] (also known to be equivalent to the graph path-widthย [LinharesYanasse02] problem) that is based on a single $\mathrm{๐๐๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐ก}$ constraint. The pattern sequencing problem can be described as follows: Given a 0-1 matrix in which each column $j$ $\left(1โคjโคp\right)$ corresponds to a product required by the customers and each row $i$ $\left(1โคiโคc\right)$ corresponds to the order of a particular customer (The entry ${c}_{ij}$ is equal to 1 if and only if customer $i$ has ordered some quantity of product $j$.), the objective is to find a permutation of the products such that the maximum number of open orders at any point in the sequence is minimised. Order $i$ is open at point $k$ in the production sequence if there is a product required in order $i$ that appears at or before position $k$ in the sequence and also a product that appears at or after position $k$ in the sequence.

Before giving the constraint model, let us first provide an instance of the pattern-sequencing problem. Consider the matrix ${\mathrm{โณ}}_{1}$ depicted by partย (A1) of Fig.ย 5.97.2. Partย (A2) gives its corresponding cumulated matrix ${\mathrm{โณ}}_{2}$ obtained by setting to 1 each 0 of ${\mathrm{โณ}}_{1}$ that is both preceded and followed by a 1. Partย (A3) depicts the corresponding solution in term of the $\mathrm{๐๐๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐ก}$ constraint: to each row of the matrix ${\mathrm{โณ}}_{1}$ corresponds a task defined as the convex hull of the different 1 located on that row. Finally partย (A4) gives the cumulated profile associated with partย (A3), namely the number of 1 in each column of ${\mathrm{โณ}}_{2}$. The cost 3 of this solution is equal to the maximum number of 1 in the columns of the cumulated matrix ${\mathrm{โณ}}_{2}$. As shown by partsย (B1-B4), we can get a lower cost of 2 by pushing the fourth column to the rightmost position.

The idea of the model is to associate to each row (i.e.,ย customer) $i$ of the cumulated matrix a stack task that starts at the first 1 on row $i$ and ends at the last 1 of row $i$ (i.e.,ย the task corresponds to the convex hull of the different 1 located on row $i$). Then the cost of a solution is simply the maximum height on the corresponding cumulated profile.

For each column $j$ of the 0-1 matrix initially given there is a variable ${V}_{j}$ ranging from 1 to the number of columns $p$. The value of ${V}_{j}$ gives the position of column $j$ in a solution. We put all the stack tasks in a $\mathrm{๐๐๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐ก}$ constraint, telling that each stack task uses one unit of the resource during all it execution. Since we want to have the same model for different limits on the maximum number of open stacks, and since all variables ${V}_{1},{V}_{2},โฏ,{V}_{p}$ have to be distinct, we have an extra dummy task characterised as the convex hull of ${V}_{1},{V}_{2},โฏ,{V}_{p}$. This extra dummy task has a height $H$ that has to be maximised. For the matrix depicted by (A1) of Fig.ย 5.97.2 we pass to the $\mathrm{๐๐๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐ก}$ constraint the following collection of tasks:

$โฉ\begin{array}{cc}\mathrm{๐๐๐๐๐๐}-โฉ{P}_{1},{P}_{2},{P}_{3},{P}_{4},{P}_{6},{P}_{7},{P}_{9}โช\hfill & \mathrm{๐๐๐๐๐๐}-1,\hfill \\ \mathrm{๐๐๐๐๐๐}-โฉ{P}_{2},{P}_{5}โช\hfill & \mathrm{๐๐๐๐๐๐}-1,\hfill \\ \mathrm{๐๐๐๐๐๐}-โฉ{P}_{4},{P}_{7},{P}_{8}โช\hfill & \mathrm{๐๐๐๐๐๐}-1,\hfill \\ \mathrm{๐๐๐๐๐๐}-โฉ{P}_{1},{P}_{2},{P}_{3},{P}_{4},{P}_{5},{P}_{6},{P}_{7},{P}_{8},{P}_{9}โช\hfill & \mathrm{๐๐๐๐๐๐}-0\hfill \end{array}โช$
Algorithm

A first natural way to handle the $\mathrm{๐๐๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐ก}$ constraint is to accumulate the compulsory partย [Lahrichi82] of the different tasks in a profile and to prune according to this profile. We give the main ideas for computing the compulsory part of a task and for pruning a task according to the profile of compulsory parts.

Compulsory part of a task Given a task $T$ characterised as the convex hull of a set of distinct points ${P}_{1},{P}_{2},โฏ,{P}_{k}$ the compulsory part of $T$ corresponds to the, possibly empty, interval $\left[{s}_{T},{e}_{T}\right]$ where:

• ${s}_{T}$ is the largest value $v$ such that, when all variables ${P}_{1},{P}_{2},โฏ,{P}_{k}$ are greater than or equal to $v$, all variables ${P}_{1},{P}_{2},โฏ,{P}_{k}$ can still take distinct values.

• ${e}_{T}$ is the smallest value $v$ such that, when all variables ${P}_{1},{P}_{2},โฏ,{P}_{k}$ are less than or equal to $v$, all variables ${P}_{1},{P}_{2},โฏ,{P}_{k}$ can still take distinct values.

Pruning according to the profile of compulsory parts Given two instants $i$ and $j$ $\left(i and a task $T$ characterised as the convex hull of a set of distinct points ${P}_{1},{P}_{2},โฏ,{P}_{k}$, assume that $T$ cannot overlap $i$ and $j$ since this would lead exceeding $\mathrm{๐ป๐ธ๐ผ๐ธ๐}$, the second argument of the $\mathrm{๐๐๐๐๐๐๐๐๐๐}_\mathrm{๐๐๐๐๐๐ก}$ constraint. Furthermore assume that, when all variables ${P}_{1},{P}_{2},โฏ,{P}_{k}$ are both greater than $i$ and less than $j$, all variables ${P}_{1},{P}_{2},โฏ,{P}_{k}$ cannot take distinct values. Then all values of $\left[i+1,j-1\right]$ can be removed from variables ${P}_{1},{P}_{2},โฏ,{P}_{k}$.

Keywords
Derived Collection
$\mathrm{๐๐๐}\left(\begin{array}{c}\mathrm{๐ธ๐ฝ๐๐๐ฐ๐ฝ๐๐}-\mathrm{๐๐๐๐๐๐๐๐๐๐}\left(\mathrm{๐๐๐๐๐๐๐}-\mathrm{๐๐๐๐}\right),\hfill \\ \mathrm{๐๐๐๐}\left(\mathrm{๐๐๐๐๐๐๐}-\mathrm{๐๐ฐ๐๐บ๐}.\mathrm{๐๐๐๐๐๐}.\mathrm{๐๐๐}\right)\right]\hfill \end{array}\right)$
Arc input(s)

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

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

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

Arc input(s)

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

Arc generator
$\mathrm{๐๐ ๐๐ท๐๐ถ๐}$$โฆ\mathrm{๐๐๐๐๐๐๐๐๐๐}\left(\mathrm{๐๐๐๐๐๐๐๐},\mathrm{๐๐๐๐๐}\right)$

Arc arity
Arc constraint(s)
$\left(\mathrm{๐๐๐๐๐๐๐๐}.\mathrm{๐๐๐๐๐๐๐},\mathrm{๐๐๐๐๐}.\mathrm{๐๐๐๐๐๐}\right)$
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 forces for each task that the set of points defining its time interval are all distinct. The second graph constraint makes sure for each time point $t$, 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.97.3 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 corresponding to a point used in the definitions of the different tasks. On the other hand, the successors of a source vertex correspond to those tasks that overlap a given time point. The $\mathrm{๐๐๐๐๐๐๐๐๐๐}_\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{๐ป๐ธ๐ผ๐ธ๐}=3$.