5.183. k_used_by_interval

DESCRIPTIONLINKSGRAPH
Origin

Derived from 𝚞𝚜𝚎𝚍_πš‹πš’_πš’πš—πšπšŽπš›πšŸπšŠπš• and from πš”_𝚞𝚜𝚎𝚍_πš‹πš’.

Constraint

πš”_𝚞𝚜𝚎𝚍_πš‹πš’_πš’πš—πšπšŽπš›πšŸπšŠπš•(πš‚π™΄πšƒπš‚,πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»)

Type
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Arguments
πš‚π™΄πšƒπš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚜𝚎𝚝-πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)
πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»πš’πš—πš
Restrictions
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>0
πš›πšŽπššπšžπš’πš›πšŽπš(πš‚π™΄πšƒπš‚,𝚜𝚎𝚝)
|πš‚π™΄πšƒπš‚|>1
πš—πš˜πš—_πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πšœπš’πš£πšŽ(πš‚π™΄πšƒπš‚,𝚜𝚎𝚝)
πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»>0
Purpose

Given |πš‚π™΄πšƒπš‚| sets of domain variables, the πš”_𝚞𝚜𝚎𝚍_πš‹πš’_πš’πš—πšπšŽπš›πšŸπšŠπš• constraint enforces a 𝚞𝚜𝚎𝚍_πš‹πš’_πš’πš—πšπšŽπš›πšŸπšŠπš• constraint between each pair of consecutive sets.

Example
𝚜𝚎𝚝-πšŸπšŠπš›-1,πšŸπšŠπš›-1,πšŸπšŠπš›-1,πšŸπšŠπš›-8,πšŸπšŠπš›-6,πšŸπšŠπš›-2,𝚜𝚎𝚝-1,0,7,7,𝚜𝚎𝚝-1,2,3

In the example, the second argument πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»=3 defines the following family of intervals [3Β·k,3Β·k+2], where k is an integer. Consequently, the πš”_𝚞𝚜𝚎𝚍_πš‹πš’_πš’πš—πšπšŽπš›πšŸπšŠπš• constraint holds since:

  • The first collection of variables is assigned 4 values in the interval [0,2] as well as 2 values in the interval [6,8], while the second collection of variables is assigned no more values in the previous two intervals.

  • The second collection of variables is assigned 2 values in the interval [0,2] as well as 2 values in the interval [6,8], while the third collection of variables is assigned no more values in the previous two intervals.

Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»>0
Symmetries
  • Items of πš‚π™΄πšƒπš‚ are permutable.

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

See also

common keyword: πš”_𝚞𝚜𝚎𝚍_πš‹πš’Β (system of constraints).

part of system of constraints: 𝚞𝚜𝚎𝚍_πš‹πš’_πš’πš—πšπšŽπš›πšŸπšŠπš•.

used in graph description: 𝚞𝚜𝚎𝚍_πš‹πš’_πš’πš—πšπšŽπš›πšŸπšŠπš•.

Keywords

constraint type: system of constraints, decomposition.

modelling: inclusion, interval.

Arc input(s)

πš‚π™΄πšƒπš‚

Arc generator
π‘ƒπ΄π‘‡π»β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(𝚜𝚎𝚝1,𝚜𝚎𝚝2)

Arc arity
Arc constraint(s)
𝚞𝚜𝚎𝚍_πš‹πš’_πš’πš—πšπšŽπš›πšŸπšŠπš•(𝚜𝚎𝚝1.𝚜𝚎𝚝,𝚜𝚎𝚝2.𝚜𝚎𝚝,πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»)
Graph property(ies)
𝐍𝐀𝐑𝐂=|πš‚π™΄πšƒπš‚|-1

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.183.1 respectively show the initial and final graph associated with the Example slot. To each vertex corresponds a collection of variables, while to each arc corresponds a 𝚞𝚜𝚎𝚍_πš‹πš’_πš’πš—πšπšŽπš›πšŸπšŠπš• constraint.

Figure 5.183.1. Initial and final graph of the πš”_𝚞𝚜𝚎𝚍_πš‹πš’_πš’πš—πšπšŽπš›πšŸπšŠπš• constraint
ctrs/k_used_by_intervalActrs/k_used_by_intervalB
(a) (b)