5.83. cumulative_convex

DESCRIPTIONLINKSGRAPH
Origin

Derived from ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ

Constraint

๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ_๐šŒ๐š˜๐š—๐šŸ๐šŽ๐šก(๐šƒ๐™ฐ๐š‚๐™บ๐š‚,๐™ป๐™ธ๐™ผ๐™ธ๐šƒ)

Type
๐™ฟ๐™พ๐™ธ๐™ฝ๐šƒ๐š‚๐šŒ๐š˜๐š•๐š•๐šŽ๐šŒ๐š๐š’๐š˜๐š—(๐šŸ๐šŠ๐š›-๐š๐šŸ๐šŠ๐š›)
Arguments
๐šƒ๐™ฐ๐š‚๐™บ๐š‚๐šŒ๐š˜๐š•๐š•๐šŽ๐šŒ๐š๐š’๐š˜๐š—(๐š™๐š˜๐š’๐š—๐š๐šœ-๐™ฟ๐™พ๐™ธ๐™ฝ๐šƒ๐š‚,๐š‘๐šŽ๐š’๐š๐š‘๐š-๐š๐šŸ๐šŠ๐š›)
๐™ป๐™ธ๐™ผ๐™ธ๐šƒ๐š’๐š—๐š
Restrictions
๐š›๐šŽ๐šš๐šž๐š’๐š›๐šŽ๐š(๐™ฟ๐™พ๐™ธ๐™ฝ๐šƒ๐š‚,๐šŸ๐šŠ๐š›)
|๐™ฟ๐™พ๐™ธ๐™ฝ๐šƒ๐š‚|>0
๐š›๐šŽ๐šš๐šž๐š’๐š›๐šŽ๐š(๐šƒ๐™ฐ๐š‚๐™บ๐š‚,[๐š™๐š˜๐š’๐š—๐š๐šœ,๐š‘๐šŽ๐š’๐š๐š‘๐š])
๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š‘๐šŽ๐š’๐š๐š‘๐šโ‰ฅ0
๐™ป๐™ธ๐™ผ๐™ธ๐šƒโ‰ฅ0
Purpose

Cumulative scheduling constraint or scheduling under resource constraints. Consider a set ๐’ฏ of tasks described by the ๐šƒ๐™ฐ๐š‚๐™บ๐š‚ 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 ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ_๐šŒ๐š˜๐š—๐šŸ๐šŽ๐šก 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
๐š™๐š˜๐š’๐š—๐š๐šœ-2,1,5๐š‘๐šŽ๐š’๐š๐š‘๐š-1,๐š™๐š˜๐š’๐š—๐š๐šœ-4,5,7๐š‘๐šŽ๐š’๐š๐š‘๐š-2,๐š™๐š˜๐š’๐š—๐š๐šœ-๐šŸ๐šŠ๐š›-14,๐šŸ๐šŠ๐š›-13,๐šŸ๐šŠ๐š›-9,๐šŸ๐šŠ๐š›-11,๐šŸ๐šŠ๐š›-10๐š‘๐šŽ๐š’๐š๐š‘๐š-2,3

Figureย 5.83.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 ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ_๐šŒ๐š˜๐š—๐šŸ๐šŽ๐šก 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 ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ_๐šŒ๐š˜๐š—๐šŸ๐šŽ๐šก constraint.

Figure 5.83.1. Points, tasks and corresponding resource consumption profile
ctrs/cumulative_convex1
Typical
|๐šƒ๐™ฐ๐š‚๐™บ๐š‚|>1
๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š‘๐šŽ๐š’๐š๐š‘๐š>0
๐™ป๐™ธ๐™ผ๐™ธ๐šƒ<๐šœ๐šž๐š–(๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š‘๐šŽ๐š’๐š๐š‘๐š)
Symmetries
  • Items of ๐šƒ๐™ฐ๐š‚๐™บ๐š‚ are permutable.

  • Items of ๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š™๐š˜๐š’๐š—๐š๐šœ are permutable.

  • ๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š‘๐šŽ๐š’๐š๐š‘๐š can be decreased to any value โ‰ฅ0.

  • ๐™ป๐™ธ๐™ผ๐™ธ๐šƒ can be increased.

Usage

A natural use of the ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ_๐šŒ๐š˜๐š—๐šŸ๐šŽ๐šก 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 ๐š–๐š’๐š—๐š’๐š–๐šž๐š–(S,โŒฉ๐šŸ๐šŠ๐š›-P 1 ,...,๐šŸ๐šŠ๐š›-P n โŒช) and a ๐š–๐šŠ๐šก๐š’๐š–๐šž๐š–(E,โŒฉ๐šŸ๐šŠ๐š›-P 1 ,...,๐šŸ๐šŠ๐š›-P n โŒช) constraints, one could replace the ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ_๐šŒ๐š˜๐š—๐šŸ๐šŽ๐šก constraint by a ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ constraint. However this hinders propagation.

As a concrete example of use of the ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ_๐šŒ๐š˜๐š—๐šŸ๐šŽ๐šก constraint we present a constraint model for a well-known pattern-sequencing problemย [FinkVoss99] (also known to be equivalent to the graph pathwidthย [LinharesYanasse02] problem) that is based on one single ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ_๐šŒ๐š˜๐š—๐šŸ๐šŽ๐šก constraint. The pattern sequencing problem can be described as follows: Given a 0-1 matrix in which each column j (1โ‰คjโ‰คp) corresponds to a product required by the customers and each row i (1โ‰คiโ‰ค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.83.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 (A2) where column 4 of (A1) is put at rightmost position
ctrs/cumulative_convex2

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.83.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 ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ_๐šŒ๐š˜๐š—๐šŸ๐šŽ๐šก 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 ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ_๐šŒ๐š˜๐š—๐šŸ๐šŽ๐šก 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.83.2 we pass to the ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ_๐šŒ๐š˜๐š—๐šŸ๐šŽ๐šก constraint the following collection of tasks:

๐š™๐š˜๐š’๐š—๐š๐šœ-โŒฉP 1 ,P 2 ,P 3 ,P 4 ,P 6 ,P 7 ,P 9 โŒช๐š‘๐šŽ๐š’๐š๐š‘๐š-1,๐š™๐š˜๐š’๐š—๐š๐šœ-โŒฉP 2 ,P 5 โŒช๐š‘๐šŽ๐š’๐š๐š‘๐š-1,๐š™๐š˜๐š’๐š—๐š๐šœ-โŒฉP 4 ,P 7 ,P 8 โŒช๐š‘๐šŽ๐š’๐š๐š‘๐š-1,๐š™๐š˜๐š’๐š—๐š๐šœ-โŒฉP 1 ,P 2 ,P 3 ,P 4 ,P 5 ,P 6 ,P 7 ,P 8 ,P 9 โŒช๐š‘๐šŽ๐š’๐š๐š‘๐š-0
Algorithm

A first natural way to handle the ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ_๐šŒ๐š˜๐š—๐šŸ๐šŽ๐šก 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 [s T ,e T ] 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 (i<j) 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 ๐™ป๐™ธ๐™ผ๐™ธ๐šƒ, the second argument of the ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ_๐šŒ๐š˜๐š—๐šŸ๐šŽ๐šก 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 [i+1,j-1] can be removed from variables P 1 ,P 2 ,...,P k .

See also

common keyword: ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽย (resource constraint).

used in graph description: ๐šŠ๐š•๐š•๐š๐š’๐š๐š๐šŽ๐š›๐šŽ๐š—๐š, ๐š‹๐šŽ๐š๐š ๐šŽ๐šŽ๐š—_๐š–๐š’๐š—_๐š–๐šŠ๐šก, ๐šœ๐šž๐š–_๐šŒ๐š๐š›.

Keywords

characteristic of a constraint: convex.

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

filtering: compulsory part.

problems: pattern sequencing.

Derived Collection
๐šŒ๐š˜๐š•๐™ธ๐™ฝ๐š‚๐šƒ๐™ฐ๐™ฝ๐šƒ๐š‚-๐šŒ๐š˜๐š•๐š•๐šŽ๐šŒ๐š๐š’๐š˜๐š—(๐š’๐š—๐šœ๐š๐šŠ๐š—๐š-๐š๐šŸ๐šŠ๐š›),๐š’๐š๐šŽ๐š–(๐š’๐š—๐šœ๐š๐šŠ๐š—๐š-๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š™๐š˜๐š’๐š—๐š๐šœ.๐šŸ๐šŠ๐š›)]
Arc input(s)

๐šƒ๐™ฐ๐š‚๐™บ๐š‚

Arc generator
๐‘†๐ธ๐ฟ๐นโ†ฆ๐šŒ๐š˜๐š•๐š•๐šŽ๐šŒ๐š๐š’๐š˜๐š—(๐š๐šŠ๐šœ๐š”๐šœ)

Arc arity
Arc constraint(s)
๐šŠ๐š•๐š•๐š๐š’๐š๐š๐šŽ๐š›๐šŽ๐š—๐š(๐š๐šŠ๐šœ๐š”๐šœ.๐š™๐š˜๐š’๐š—๐š๐šœ)
Graph property(ies)
๐๐€๐‘๐‚=|๐šƒ๐™ฐ๐š‚๐™บ๐š‚|

Arc input(s)

๐™ธ๐™ฝ๐š‚๐šƒ๐™ฐ๐™ฝ๐šƒ๐š‚ ๐šƒ๐™ฐ๐š‚๐™บ๐š‚

Arc generator
๐‘ƒ๐‘…๐‘‚๐ท๐‘ˆ๐ถ๐‘‡โ†ฆ๐šŒ๐š˜๐š•๐š•๐šŽ๐šŒ๐š๐š’๐š˜๐š—(๐š’๐š—๐šœ๐š๐šŠ๐š—๐š๐šœ,๐š๐šŠ๐šœ๐š”๐šœ)

Arc arity
Arc constraint(s)
๐š‹๐šŽ๐š๐š ๐šŽ๐šŽ๐š—_๐š–๐š’๐š—_๐š–๐šŠ๐šก(๐š’๐š—๐šœ๐š๐šŠ๐š—๐š๐šœ.๐š’๐š—๐šœ๐š๐šŠ๐š—๐š,๐š๐šŠ๐šœ๐š”๐šœ.๐š™๐š˜๐š’๐š—๐š๐šœ)
Graph class
โ€ข ๐™ฐ๐™ฒ๐šˆ๐™ฒ๐™ป๐™ธ๐™ฒ
โ€ข ๐™ฑ๐™ธ๐™ฟ๐™ฐ๐š๐šƒ๐™ธ๐šƒ๐™ด
โ€ข ๐™ฝ๐™พ_๐™ป๐™พ๐™พ๐™ฟ

Sets
๐–ฒ๐–ด๐–ข๐–ขโ†ฆ๐šœ๐š˜๐šž๐š›๐šŒ๐šŽ,๐šŸ๐šŠ๐š›๐š’๐šŠ๐š‹๐š•๐šŽ๐šœ-๐šŒ๐š˜๐š•๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚-๐šŒ๐š˜๐š•๐š•๐šŽ๐šŒ๐š๐š’๐š˜๐š—(๐šŸ๐šŠ๐š›-๐š๐šŸ๐šŠ๐š›),๐š’๐š๐šŽ๐š–(๐šŸ๐šŠ๐š›-๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š‘๐šŽ๐š’๐š๐š‘๐š)]

Constraint(s) on sets
๐šœ๐šž๐š–_๐šŒ๐š๐š›(๐šŸ๐šŠ๐š›๐š’๐šŠ๐š‹๐š•๐šŽ๐šœ,โ‰ค,๐™ป๐™ธ๐™ผ๐™ธ๐šƒ)
Graph model

The first graph constraint enforces 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.83.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 ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ_๐šŒ๐š˜๐š—๐šŸ๐šŽ๐šก constraint holds since, for each successor set ๐’ฎ of the final graph, the sum of the heights of the tasks in ๐’ฎ does not exceed the limit ๐™ป๐™ธ๐™ผ๐™ธ๐šƒ=3.

Figure 5.83.3. Initial and final graph of the ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ_๐šŒ๐š˜๐š—๐šŸ๐šŽ๐šก constraint
ctrs/cumulative_convexA
(a)
ctrs/cumulative_convexB
(b)