Derived from $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}$

$\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}\_\mathrm{𝚌𝚘𝚗𝚟𝚎𝚡}(\mathrm{𝚃𝙰𝚂𝙺𝚂},\mathrm{𝙻𝙸𝙼𝙸𝚃})$

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.

Figure 5.97.1. Points defining the three tasks of the Example slot and corresponding resource consumption profile (note that the vertical position of a task does not really matter but is only used for displaying the contribution of a task to the resource consumption profile)

• Items of $\mathrm{𝚃𝙰𝚂𝙺𝚂}$ are permutable.

• Items of $\mathrm{𝚃𝙰𝚂𝙺𝚂}.\mathrm{𝚙𝚘𝚒𝚗𝚝𝚜}$ are permutable.

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

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

Contractible wrt. $\mathrm{𝚃𝙰𝚂𝙺𝚂}$.

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,\cdots ,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{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$$(S,\langle \mathrm{𝚟𝚊𝚛}-P_1,\cdots ,\mathrm{𝚟𝚊𝚛}-P_n\rangle )$ and a $\mathrm{𝚖𝚊𝚡𝚒𝚖𝚞𝚖}$$(E,\langle \mathrm{𝚟𝚊𝚛}-P_1,\cdots ,\mathrm{𝚟𝚊𝚛}-P_n\rangle )$ 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$ $(1\le j\le p)$ corresponds to a product required by the customers and each row $i$ $(1\le i\le c)$ 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.

Figure 5.97.2. An input matrix for the pattern sequencing problem (A1), its corresponding cumulated matrix (A2), a view in term of tasks (A3) and the corresponding cumulative profile (A4); a second matrix (B1) where column 4 of (A1) is put at the rightmost position.

Before giving the constraint model, let us first provide an instance of the pattern-sequencing problem. Consider the matrix ${ℳ}_1$ depicted by part (A1) of Fig. 5.97.2. Part (A2) gives its corresponding cumulated matrix ${ℳ}_2$ obtained by setting to 1 each 0 of ${ℳ}_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 ${ℳ}_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 ${ℳ}_2$. The cost 3 of this solution is equal to the maximum number of 1 in the columns of the cumulated matrix ${ℳ}_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,\cdots ,V_p$ have to be distinct, we have an extra dummy task characterised as the convex hull of $V_1,V_2,\cdots ,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:

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,\cdots ,P_k$ the compulsory part of $T$ corresponds to the, possibly empty, interval $[s_T,e_T]$ where:

• $s_T$ is the largest value $v$ such that, when all variables $P_1,P_2,\cdots ,P_k$ are greater than or equal to $v$, all variables $P_1,P_2,\cdots ,P_k$ can still take distinct values.

• $e_T$ is the smallest value $v$ such that, when all variables $P_1,P_2,\cdots ,P_k$ are less than or equal to $v$, all variables $P_1,P_2,\cdots ,P_k$ can still take distinct values.

Pruning according to the profile of compulsory parts Given two instants $i$ and $j$ $(i<j)$ and a task $T$ characterised as the convex hull of a set of distinct points $P_1,P_2,\cdots ,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,\cdots ,P_k$ are both greater than $i$ and less than $j$, all variables $P_1,P_2,\cdots ,P_k$ cannot take distinct values. Then all values of $[i+1,j-1]$ can be removed from variables $P_1,P_2,\cdots ,P_k$.

common keyword: $\mathrm{𝚌𝚞𝚖𝚞𝚕𝚊𝚝𝚒𝚟𝚎}$ (resource constraint).

used in graph description: $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$, $\mathrm{𝚋𝚎𝚝𝚠𝚎𝚎𝚗}\_\mathrm{𝚖𝚒𝚗}\_\mathrm{𝚖𝚊𝚡}$, $\mathrm{𝚜𝚞𝚖}\_\mathrm{𝚌𝚝𝚛}$.

characteristic of a constraint: convex.

constraint type: scheduling constraint, resource constraint, temporal constraint.

filtering: compulsory part.

problems: pattern sequencing.