5.10. alldifferent_interval

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Derived from πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš.

Constraint

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

Synonyms

πšŠπš•πš•πšπš’πšπš_πš’πš—πšπšŽπš›πšŸπšŠπš•, πšŠπš•πš•πšπš’πšœπšπš’πš—πšŒπš_πš’πš—πšπšŽπš›πšŸπšŠπš•.

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

Enforce all variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ to belong to distinct intervals. The intervals are defined by [πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»Β·k,πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»Β·k+πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»-1] where k is an integer.

Example
(2,4,10,3)

In the example, the second argument πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»=3 defines the following family of intervals [3Β·k,3Β·k+2], where k is an integer. Since the three variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ take values that are respectively located within the three following distinct intervals [0,2], [3,5] and [9,11], the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš’πš—πšπšŽπš›πšŸπšŠπš• constraint holds.

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

  • A value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› that belongs to the k-th interval, of size πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™», can be renamed to any unused value of the same interval.

  • Two distinct values of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› that belong to two distinct intervals, of size πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™», can be swapped.

See also

implied by: πšŠπš•πš•_πš–πš’πš—_πšπš’πšœπš.

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

Keywords

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

constraint type: value constraint.

filtering: arc-consistency.

final graph structure: one_succ.

modelling: interval.

Arc input(s)

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

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

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

Graph class
𝙾𝙽𝙴_πš‚πš„π™²π™²

Graph model

Similar to the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint, but we replace the binary equality constraint of the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraint by the fact that two variables are respectively assigned to two values that belong to the same interval. We generate a clique with a belong to the same interval constraint between each pair of vertices (including a vertex and itself) and state that the size of the largest strongly connected component should not exceed 1.

PartsΒ (A) andΒ (B) of FigureΒ 5.10.1 respectively show the initial and final graph associated with the Example slot. Since we use the πŒπ€π—_𝐍𝐒𝐂𝐂 graph property we show one of the largest strongly connected component of the final graph.

Figure 5.10.1. Initial and final graph of the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš’πš—πšπšŽπš›πšŸπšŠπš• constraint
ctrs/alldifferent_intervalActrs/alldifferent_intervalB
(a) (b)
Automaton

FigureΒ 5.10.2 depicts the automaton associated with the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš’πš—πšπšŽπš›πšŸπšŠπš• constraint. To each item of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds a signature variable πš‚ i that is equal to 1. For each interval [πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»Β·k,πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»Β·k+πš‚π™Έπš‰π™΄_π™Έπ™½πšƒπ™΄πšπš…π™°π™»-1] of values the automaton counts the number of occurrences of its values and finally imposes that the values of an interval are taken at most once.

Figure 5.10.2. Automaton of the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš_πš’πš—πšπšŽπš›πšŸπšŠπš• constraint
ctrs/alldifferent_interval1