5.229. ninterval

DESCRIPTIONLINKSGRAPH
Origin

Derived from πš—πšŸπšŠπš•πšžπšŽ.

Constraint

πš—πš’πš—πšπšŽπš›πšŸπšŠπš•(π™½πš…π™°π™»,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»)

Arguments
π™½πš…π™°π™»πšπšŸπšŠπš›
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»πš’πš—πš
Restrictions
π™½πš…π™°π™»β‰₯πš–πš’πš—(1,|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|)
π™½πš…π™°π™»β‰€|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»>0
Purpose

Consider the intervals of the form [πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»Β·k,πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»Β·k+πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»-1] where k is an integer. π™½πš…π™°π™» is the number of intervals for which at least one value is assigned to at least one variable of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

Example
(2,3,1,9,1,9,4)

In the example, the third argument πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»=4 defines the following family of intervals [4Β·k,4Β·k+3], where k is an integer. Values 3, 1, 9, 1 and 9 are respectively located within intervals [0,3], [0,3], [8,11], [0,3] and [8,11]. Since we only use the two intervals [0,3] and [8,11] the first argument of the πš—πš’πš—πšπšŽπš›πšŸπšŠπš• constraint is set to value 2.

Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are permutable.

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

Usage

The πš—πš’πš—πšπšŽπš›πšŸπšŠπš• constraint is useful for counting the number of effectively used periods, no matter how many time each period is used. A period can for example stand for a hour or for a day.

Algorithm

[Beldiceanu01], [BeldiceanuCarlssonThiel02].

See also

related: πš—πšŒπš•πšŠπšœπšœΒ (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ/πšŒπš˜πš—πšœπšπšŠπš—πš replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽβˆˆπš™πšŠπš›πšπš’πšπš’πš˜πš—), πš—πšŽπššπšžπš’πšŸπšŠπš•πšŽπš—πšŒπšŽΒ (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ/πšŒπš˜πš—πšœπšπšŠπš—πš replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ mod πšŒπš˜πš—πšœπšπšŠπš—πš), πš—πš™πšŠπš’πš›Β (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ/πšŒπš˜πš—πšœπšπšŠπš—πš replaced by πš™πšŠπš’πš› of πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ).

specialisation: πš—πšŸπšŠπš•πšžπšŽΒ (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ/πšŒπš˜πš—πšœπšπšŠπš—πš replaced by πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ).

Keywords

constraint type: counting constraint, value partitioning constraint.

final graph structure: strongly connected component, equivalence.

modelling: number of distinct equivalence classes, interval.

Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›/πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›/πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»
Graph property(ies)
𝐍𝐒𝐂𝐂=π™½πš…π™°π™»

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.229.1 respectively show the initial and final graph associated with the Example slot. Since we use the 𝐍𝐒𝐂𝐂 graph property we show the different strongly connected components of the final graph. Each strongly connected component corresponds to those values of an interval that are assigned to some variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection. The values 1, 3 and the value 9, which respectively correspond to intervals [0,3] and [8,11], are assigned to the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection.

Figure 5.229.1. Initial and final graph of the πš—πš’πš—πšπšŽπš›πšŸπšŠπš• constraint
ctrs/nintervalActrs/nintervalB
(a) (b)