5.168. interval_and_count

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

[Cousin93]

Constraint

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

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

First consider the set of tasks of the ๐šƒ๐™ฐ๐š‚๐™บ๐š‚ collection, where each task has a specific colour that may not be initially fixed. Then consider the intervals of the form [kยท๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป,kยท๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป+๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป-1], where k is an integer. The ๐š’๐š—๐š๐šŽ๐š›๐šŸ๐šŠ๐š•_๐šŠ๐š—๐š_๐šŒ๐š˜๐šž๐š—๐š constraint enforces that, for each interval I k previously defined, the total number of tasks, which both are assigned to I k and take their colour in ๐™ฒ๐™พ๐™ป๐™พ๐š„๐š๐š‚, does not exceed the limit ๐™ฐ๐šƒ๐™ผ๐™พ๐š‚๐šƒ.

Example
2,4,๐š˜๐š›๐š’๐š๐š’๐š—-1๐šŒ๐š˜๐š•๐š˜๐šž๐š›-4,๐š˜๐š›๐š’๐š๐š’๐š—-0๐šŒ๐š˜๐š•๐š˜๐šž๐š›-9,๐š˜๐š›๐š’๐š๐š’๐š—-10๐šŒ๐š˜๐š•๐š˜๐šž๐š›-4,๐š˜๐š›๐š’๐š๐š’๐š—-4๐šŒ๐š˜๐š•๐š˜๐šž๐š›-4,5

Figureย 5.168.1 shows the solution associated with the example. The constraint ๐š’๐š—๐š๐šŽ๐š›๐šŸ๐šŠ๐š•_๐šŠ๐š—๐š_๐šŒ๐š˜๐šž๐š—๐š holds since, for each interval, the number of tasks taking colour 4 does not exceed the limit 2.

Figure 5.168.1. Solution with the use of each interval
ctrs/interval_and_count1
Typical
๐™ฐ๐šƒ๐™ผ๐™พ๐š‚๐šƒ>0
|๐™ฒ๐™พ๐™ป๐™พ๐š„๐š๐š‚|>0
|๐šƒ๐™ฐ๐š‚๐™บ๐š‚|>1
๐š›๐šŠ๐š—๐š๐šŽ(๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐š˜๐š›๐š’๐š๐š’๐š—)>1
๐š›๐šŠ๐š—๐š๐šŽ(๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐šŒ๐š˜๐š•๐š˜๐šž๐š›)>1
๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป>1
Symmetries
  • ๐™ฐ๐šƒ๐™ผ๐™พ๐š‚๐šƒ can be increased.

  • Items of ๐™ฒ๐™พ๐™ป๐™พ๐š„๐š๐š‚ are permutable.

  • 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.

  • An occurrence of a value of ๐šƒ๐™ฐ๐š‚๐™บ๐š‚.๐šŒ๐š˜๐š•๐š˜๐šž๐š› that belongs to ๐™ฒ๐™พ๐™ป๐™พ๐š„๐š๐š‚.๐šŸ๐šŠ๐š• (resp. does not belong to ๐™ฒ๐™พ๐™ป๐™พ๐š„๐š๐š‚.๐šŸ๐šŠ๐š•) can be replaced by any other value in ๐™ฒ๐™พ๐™ป๐™พ๐š„๐š๐š‚.๐šŸ๐šŠ๐š• (resp. not in ๐™ฒ๐™พ๐™ป๐™พ๐š„๐š๐š‚.๐šŸ๐šŠ๐š•).

Usage

This constraint was originally proposed for dealing with timetabling problems. In this context the different intervals are interpreted as morning and afternoon periods of different consecutive days. Each colour corresponds to a type of course (i.e.,ย French, mathematics). There is a restriction on the maximum number of courses of a given type each morning as well as each afternoon.

Remark

If we want to only consider intervals that correspond to the morning or to the afternoon we could extend the ๐š’๐š—๐š๐šŽ๐š›๐šŸ๐šŠ๐š•_๐šŠ๐š—๐š_๐šŒ๐š˜๐šž๐š—๐š constraint in the following way:

  • We introduce two extra parameters ๐š๐™ด๐š‚๐šƒ and ๐š€๐š„๐™พ๐šƒ๐™ธ๐™ด๐™ฝ๐šƒ that correspond to non-negative integers such that ๐š๐™ด๐š‚๐šƒ is strictly less than ๐š€๐š„๐™พ๐šƒ๐™ธ๐™ด๐™ฝ๐šƒ,

  • We add the following condition to the arc constraint: (๐š๐šŠ๐šœ๐š”๐šœ1.๐š˜๐š›๐š’๐š๐š’๐š—/๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป)โ‰ก๐š๐™ด๐š‚๐šƒ( mod ๐š€๐š„๐™พ๐šƒ๐™ธ๐™ด๐™ฝ๐šƒ)

Now, if we want to express a constraint on the morning intervals, we set ๐š๐™ด๐š‚๐šƒ to 0 and ๐š€๐š„๐™พ๐šƒ๐™ธ๐™ด๐™ฝ๐šƒ to 2.

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,|๐šƒ๐™ฐ๐š‚๐™บ๐š‚|]) of the ๐šƒ๐™ฐ๐š‚๐™บ๐š‚ collection we create a 0-1 variable B i that will be set to 1 if and only if task ๐šƒ๐™ฐ๐š‚๐™บ๐š‚[i] takes a colour within the set of colours ๐™ฒ๐™พ๐™ป๐™พ๐š„๐š๐š‚:

    B i โ‡”๐šƒ๐™ฐ๐š‚๐™บ๐š‚[i].๐šŒ๐š˜๐š•๐š˜๐šž๐š›=๐™ฒ๐™พ๐™ป๐™พ๐š„๐š๐š‚[1].๐šŸ๐šŠ๐š• โˆจ

    ย ย ย ย ย ย ย ๐šƒ๐™ฐ๐š‚๐™บ๐š‚[i].๐šŒ๐š˜๐š•๐š˜๐šž๐š›=๐™ฒ๐™พ๐™ป๐™พ๐š„๐š๐š‚[2].๐šŸ๐šŠ๐š• โˆจ

    ย ย ย ย ย ย ย ..............................

    ย ย ย ย ย ย ย ๐šƒ๐™ฐ๐š‚๐™บ๐š‚[i].๐šŒ๐š˜๐š•๐š˜๐šž๐š›=๐™ฒ๐™พ๐™ป๐™พ๐š„๐š๐š‚[|๐™ฒ๐™พ๐™ป๐™พ๐š„๐š๐š‚|].๐šŸ๐šŠ๐š•.

  2. 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, both task ๐šƒ๐™ฐ๐š‚๐™บ๐š‚[i] takes a colour within the set of colours ๐™ฒ๐™พ๐™ป๐™พ๐š„๐š๐š‚, and the origin of task ๐šƒ๐™ฐ๐š‚๐™บ๐š‚[i] is assigned within interval [kยท๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป,kยท๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป+๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป-1]:

    B ik โ‡”B i โˆง

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

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

  3. Finally, for each interval [kยท๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป,kยท๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป+๐š‚๐™ธ๐š‰๐™ด_๐™ธ๐™ฝ๐šƒ๐™ด๐š๐š…๐™ฐ๐™ป-1] (kโˆˆ[0,K]), we impose the sum B 1k +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: coloured, 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
๐šŠ๐š–๐š˜๐š—๐š_๐š•๐š˜๐š _๐šž๐š™(0,๐™ฐ๐šƒ๐™ผ๐™พ๐š‚๐šƒ,๐šŸ๐šŠ๐š›๐š’๐šŠ๐š‹๐š•๐šŽ๐šœ,๐™ฒ๐™พ๐™ป๐™พ๐š„๐š๐š‚)
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 an ๐šŠ๐š–๐š˜๐š—๐š_๐š•๐š˜๐š _๐šž๐š™ constraint on each set ๐’ฎ of successors of the different vertices of the final graph. This put a restriction on the maximum number of tasks of ๐’ฎ for which the colour attribute takes its value in ๐™ฒ๐™พ๐™ป๐™พ๐š„๐š๐š‚.

Partsย (A) andย (B) of Figureย 5.168.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.168.2. Initial and final graph of the ๐š’๐š—๐š๐šŽ๐š›๐šŸ๐šŠ๐š•_๐šŠ๐š—๐š_๐šŒ๐š˜๐šž๐š—๐š constraint
ctrs/interval_and_countActrs/interval_and_countB
(a) (b)
Automaton

Figureย 5.168.3 depicts the automaton associated with the ๐š’๐š—๐š๐šŽ๐š›๐šŸ๐šŠ๐š•_๐šŠ๐š—๐š_๐šŒ๐š˜๐šž๐š—๐š constraint. Let ๐™ฒ๐™พ๐™ป๐™พ๐š„๐š i be the ๐šŒ๐š˜๐š•๐š˜๐šž๐š› attribute of the i th item of the ๐šƒ๐™ฐ๐š‚๐™บ๐š‚ collection. To each pair (๐™ฒ๐™พ๐™ป๐™พ๐š„๐š๐š‚,๐™ฒ๐™พ๐™ป๐™พ๐š„๐š i ) corresponds a signature variable ๐š‚ i as well as the following signature constraint: ๐™ฒ๐™พ๐™ป๐™พ๐š„๐š i โˆˆ๐™ฒ๐™พ๐™ป๐™พ๐š„๐š๐š‚โ‡”๐š‚ i .

Figure 5.168.3. Automaton of the ๐š’๐š—๐š๐šŽ๐š›๐šŸ๐šŠ๐š•_๐šŠ๐š—๐š_๐šŒ๐š˜๐šž๐š—๐š constraint
ctrs/interval_and_count2