5.169. interval_and_sum

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

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

Constraint

๐š’๐š—๐š๐šŽ๐š›๐šŸ๐šŠ๐š•_๐šŠ๐š—๐š_๐šœ๐šž๐š–(๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป,๐šƒ๐™ฐ๐š‚๐™บ๐š‚,๐™ป๐™ธ๐™ผ๐™ธ๐šƒ)

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

A maximum resource capacity constraint: We have to fix the origins of a collection of tasks in such a way that, for all the tasks that are allocated to the same interval, the sum of the heights does not exceed a given capacity. All the intervals we consider have the following form: [kยท๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป,kยท๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป+๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป-1], where k is an integer.

Example
5,๐š˜๐š›๐š’๐š๐š’๐š—-1๐š‘๐šŽ๐š’๐š๐š‘๐š-2,๐š˜๐š›๐š’๐š๐š’๐š—-10๐š‘๐šŽ๐š’๐š๐š‘๐š-2,๐š˜๐š›๐š’๐š๐š’๐š—-10๐š‘๐šŽ๐š’๐š๐š‘๐š-3,๐š˜๐š›๐š’๐š๐š’๐š—-4๐š‘๐šŽ๐š’๐š๐š‘๐š-1,5

Figureย 5.169.1 shows the solution associated with the example. The constraint ๐š’๐š—๐š๐šŽ๐š›๐šŸ๐šŠ๐š•_๐šŠ๐š—๐š_๐šœ๐šž๐š– holds since the sum of the heights of the tasks that are located in the same interval does not exceed the limit 5. Each task t is depicted by a rectangle r associated with the interval to which the task t is assigned. The rectangle r is labelled with the position of t within the items of the ๐šƒ๐™ฐ๐š‚๐™บ๐š‚ collection. The origin of task t is represented by a small black square located within its corresponding rectangle r. Finally, the height of a rectangle r is equal to the height of the task t to which it corresponds.

Figure 5.169.1. Solution showing for each interval the corresponding tasks
ctrs/interval_and_sum1
Typical
๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป>1
|๐šƒ๐™ฐ๐š‚๐™บ๐š‚|>1
๐š›๐šŠ๐š—๐š๐šŽ(๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š˜๐š›๐š’๐š๐š’๐š—)>1
๐š›๐šŠ๐š—๐š๐šŽ(๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š‘๐šŽ๐š’๐š๐š‘๐š)>1
๐™ป๐™ธ๐™ผ๐™ธ๐šƒ<๐šœ๐šž๐š–(๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š‘๐šŽ๐š’๐š๐š‘๐š)
Symmetries
  • Items of ๐šƒ๐™ฐ๐š‚๐™บ๐š‚ are permutable.

  • One and the same constant can be added to the ๐š˜๐š›๐š’๐š๐š’๐š— attribute of all items of ๐šƒ๐™ฐ๐š‚๐™บ๐š‚.

  • An occurrence of a value of ๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š˜๐š›๐š’๐š๐š’๐š— that belongs to the k-th interval, of size ๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป, can be replaced by any other value of the same interval.

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

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

Usage

This constraint can be use for timetabling problems. In this context the different intervals are interpreted as morning and afternoon periods of different consecutive days. We have a capacity constraint for all tasks that are assigned to the same morning or afternoon of a given day.

Reformulation

Let K denote the index of the last possible interval where the tasks can be assigned: K=โŒŠmax iโˆˆ[1,|๐šƒ๐™ฐ๐š‚๐™บ๐š‚|] (๐šƒ๐™ฐ๐š‚๐™บ๐š‚[i].๐š˜๐š›๐š’๐š๐š’๐š— ยฏ)+๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป-1 ๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ปโŒ‹. The ๐š’๐š—๐š๐šŽ๐š›๐šŸ๐šŠ๐š•_๐šŠ๐š—๐š_๐šœ๐šž๐š–(๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป,๐šƒ๐™ฐ๐š‚๐™บ๐š‚,๐™ป๐™ธ๐™ผ๐™ธ๐šƒ) constraint can be expressed in term of a set of reified constraints and of K arithmetic constraints (i.e.,ย ๐šœ๐šŒ๐šŠ๐š•๐šŠ๐š›_๐š™๐š›๐š˜๐š๐šž๐šŒ๐š constraints).

  1. For each task ๐šƒ๐™ฐ๐š‚๐™บ๐š‚[i] (iโˆˆ[1,|๐šƒ๐™ฐ๐š‚๐™บ๐š‚|]) and for each interval [kยท๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป,kยท๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป+๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป-1] (kโˆˆ[0,K]) we create a 0-1 variable B ik that will be set to 1 if and only if the origin of task ๐šƒ๐™ฐ๐š‚๐™บ๐š‚[i] is assigned within interval [kยท๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป,kยท๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป+๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป-1]:

    B ik โ‡”๐šƒ๐™ฐ๐š‚๐™บ๐š‚[i].๐š˜๐š›๐š’๐š๐š’๐š—โ‰ฅkยท๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป โˆง

    ย ย ย ย ย ย ย ย ๐šƒ๐™ฐ๐š‚๐™บ๐š‚[i].๐š˜๐š›๐š’๐š๐š’๐š—โ‰คkยท๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป+๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป-1

  2. Finally, for each interval [kยท๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป,kยท๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป+๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป-1] (kโˆˆ[0,K]), we impose the sum ๐šƒ๐™ฐ๐š‚๐™บ๐š‚[1].๐š‘๐šŽ๐š’๐š๐š‘๐šยทB 1k +๐šƒ๐™ฐ๐š‚๐™บ๐š‚[2].๐š‘๐šŽ๐š’๐š๐š‘๐šยทB 2k +...+๐šƒ๐™ฐ๐š‚๐™บ๐š‚[|๐šƒ๐™ฐ๐š‚๐™บ๐š‚|].๐š‘๐šŽ๐š’๐š๐š‘๐šยทB |๐šƒ๐™ฐ๐š‚๐™บ๐š‚|k to not exceed the maximum allowed capacity ๐™ป๐™ธ๐™ผ๐™ธ๐šƒ.

See also

assignment dimension removed: ๐šœ๐šž๐š–_๐šŒ๐š๐š›ย (assignment dimension corresponding to intervals is removed).

related: ๐š’๐š—๐š๐šŽ๐š›๐šŸ๐šŠ๐š•_๐šŠ๐š—๐š_๐šŒ๐š˜๐šž๐š—๐šย (๐šœ๐šž๐š–_๐šŒ๐š๐š› constraint replaced by ๐šŠ๐š–๐š˜๐š—๐š_๐š•๐š˜๐š _๐šž๐š™).

used in graph description: ๐šœ๐šž๐š–_๐šŒ๐š๐š›.

Keywords

application area: assignment.

characteristic of a constraint: automaton, automaton with array of counters.

constraint type: timetabling constraint, resource constraint, temporal constraint.

modelling: assignment dimension, interval.

Arc input(s)

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

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

Arc arity
Arc constraint(s)
๐š๐šŠ๐šœ๐š”๐šœ1.๐š˜๐š›๐š’๐š๐š’๐š—/๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป=๐š๐šŠ๐šœ๐š”๐šœ2.๐š˜๐š›๐š’๐š๐š’๐š—/๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป
Sets
๐–ฒ๐–ด๐–ข๐–ขโ†ฆ๐šœ๐š˜๐šž๐š›๐šŒ๐šŽ,๐šŸ๐šŠ๐š›๐š’๐šŠ๐š‹๐š•๐šŽ๐šœ-๐šŒ๐š˜๐š•๐š…๐™ฐ๐š๐™ธ๐™ฐ๐™ฑ๐™ป๐™ด๐š‚-๐šŒ๐š˜๐š•๐š•๐šŽ๐šŒ๐š๐š’๐š˜๐š—(๐šŸ๐šŠ๐š›-๐š๐šŸ๐šŠ๐š›),๐š’๐š๐šŽ๐š–(๐šŸ๐šŠ๐š›-๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š‘๐šŽ๐š’๐š๐š‘๐š)]

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

We use a bipartite graph where each class of vertices corresponds to the different tasks of the ๐šƒ๐™ฐ๐š‚๐™บ๐š‚ collection. There is an arc between two tasks if their origins belong to the same interval. Finally we enforce a ๐šœ๐šž๐š–_๐šŒ๐š๐š› constraint on each set ๐’ฎ of successors of the different vertices of the final graph. This put a restriction on the maximum value of the sum of the ๐š‘๐šŽ๐š’๐š๐š‘๐š attributes of the tasks of ๐’ฎ.

Partsย (A) andย (B) of Figureย 5.169.2 respectively show the initial and final graph associated with the Example slot. Each connected component of the final graph corresponds to items that are all assigned to the same interval.

Figure 5.169.2. Initial and final graph of the ๐š’๐š—๐š๐šŽ๐š›๐šŸ๐šŠ๐š•_๐šŠ๐š—๐š_๐šœ๐šž๐š– constraint
ctrs/interval_and_sumActrs/interval_and_sumB
(a) (b)
Automaton

Figureย 5.169.3 depicts the automaton associated with the ๐š’๐š—๐š๐šŽ๐š›๐šŸ๐šŠ๐š•_๐šŠ๐š—๐š_๐šœ๐šž๐š– constraint. To each item of the collection ๐šƒ๐™ฐ๐š‚๐™บ๐š‚ corresponds a signature variable ๐š‚ i that is equal to 1.

Figure 5.169.3. Automaton of the ๐š’๐š—๐š๐šŽ๐š›๐šŸ๐šŠ๐š•_๐šŠ๐š—๐š_๐šœ๐šž๐š– constraint
ctrs/interval_and_sum2