5.179. k_same_interval

DESCRIPTIONLINKSGRAPH
Origin

Derived from πšœπšŠπš–πšŽ_πš’πš—πšπšŽπš›πšŸπšŠπš• and from πš”_πšœπšŠπš–πšŽ.

Constraint

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

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

Given a collection of |πš‚π™΄πšƒπš‚| sets, each containing the same number of domain variables, the πš”_πšœπšŠπš–πšŽ_πš’πš—πšπšŽπš›πšŸπšŠπš• constraint enforces a πšœπšŠπš–πšŽ_πš’πš—πšπšŽπš›πšŸπšŠπš• constraint between each pair of consecutive sets.

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

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

  • The first and second collections of variables are assigned 4 values in the interval [0,2] as well as 2 values in the interval [6,8].

  • The second and third collections of variables are also assigned 4 values in the interval [0,2] as well as 2 values in the interval [6,8].

Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»>1
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

combinatorial object: permutation.

constraint type: system of constraints, decomposition.

modelling: 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.179.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.179.1. Initial and final graph of the πš”_πšœπšŠπš–πšŽ_πš’πš—πšπšŽπš›πšŸπšŠπš• constraint
ctrs/k_same_intervalActrs/k_same_intervalB
(a) (b)