5.55. circular_change

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Derived from πšŒπš‘πšŠπš—πšπšŽ.

Constraint

πšŒπš’πš›πšŒπšžπš•πšŠπš›_πšŒπš‘πšŠπš—πšπšŽ(𝙽𝙲𝙷𝙰𝙽𝙢𝙴,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,π™²πšƒπš)

Arguments
π™½π™²π™·π™°π™½π™Άπ™΄πšπšŸπšŠπš›
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
π™²πšƒπšπšŠπšπš˜πš–
Restrictions
𝙽𝙲𝙷𝙰𝙽𝙢𝙴β‰₯0
𝙽𝙲𝙷𝙰𝙽𝙢𝙴≀|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
π™²πšƒπšβˆˆ[=,β‰ ,<,β‰₯,>,≀]
Purpose

𝙽𝙲𝙷𝙰𝙽𝙢𝙴 is the number of times that π™²πšƒπš holds on consecutive variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚. The last and the first variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are also considered to be consecutive.

Example
(4,4,4,3,4,1,β‰ )

In the example the changes within the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚=〈4,4,3,4,1βŒͺ collection are located between values 4 and 3, 3 and 4, 4 and 1, and 1 and 4 (i.e.,Β since the third argument π™²πšƒπš of the πšŒπš’πš›πšŒπšžπš•πšŠπš›_πšŒπš‘πšŠπš—πšπšŽ constraint is set to β‰ , we count one change for each disequality constraint between two consecutive variables that holds). Consequently, the corresponding πšŒπš’πš›πšŒπšžπš•πšŠπš›_πšŒπš‘πšŠπš—πšπšŽ constraint holds since its first argument 𝙽𝙲𝙷𝙰𝙽𝙢𝙴 is fixed to 4.

Typical
𝙽𝙲𝙷𝙰𝙽𝙢𝙴>0
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
πš›πšŠπš—πšπšŽ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›)>1
Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ can be shifted.

  • One and the same constant can be added to the πšŸπšŠπš› attribute of all items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

See also

common keyword: πšŒπš‘πšŠπš—πšπšŽΒ (number of changes).

Keywords

characteristic of a constraint: cyclic, automaton, automaton with counters.

constraint network structure: circular sliding cyclic(1) constraint network(2).

constraint type: timetabling constraint.

modelling: number of changes.

Arc input(s)

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

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

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš› π™²πšƒπš πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›
Graph property(ies)
𝐍𝐀𝐑𝐂=𝙽𝙲𝙷𝙰𝙽𝙢𝙴

Graph model

Since we are also interested in the constraint that links the last and the first variable we use the arc generator πΆπΌπ‘…πΆπ‘ˆπΌπ‘‡ to produce the arcs of the initial graph.

PartsΒ (A) andΒ (B) of FigureΒ 5.55.1 respectively show the initial and final graph associated with the Example slot. Since we use the 𝐍𝐀𝐑𝐂 graph property, the arcs of the final graph are stressed in bold.

Figure 5.55.1. Initial and final graph of the πšŒπš’πš›πšŒπšžπš•πšŠπš›_πšŒπš‘πšŠπš—πšπšŽ constraint
ctrs/circular_changeActrs/circular_changeB
(a) (b)
Automaton

FigureΒ 5.55.2 depicts the automaton associated with the πšŒπš’πš›πšŒπšžπš•πšŠπš›_πšŒπš‘πšŠπš—πšπšŽ constraint. To each pair of consecutive variables (πš…π™°πš i ,πš…π™°πš (i mod |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|)+1 ) of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds a 0-1 signature variable πš‚ i . The following signature constraint links πš…π™°πš i , πš…π™°πš (i mod |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|)+1 and πš‚ i : πš…π™°πš i π™²πšƒπš πš…π™°πš (i mod |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|)+1 β‡”πš‚ i .

Figure 5.55.2. Automaton of the πšŒπš’πš›πšŒπšžπš•πšŠπš›_πšŒπš‘πšŠπš—πšπšŽ constraint
ctrs/circular_change1
Figure 5.55.3. Hypergraph of the reformulation corresponding to the automaton of the πšŒπš’πš›πšŒπšžπš•πšŠπš›_πšŒπš‘πšŠπš—πšπšŽ constraint
ctrs/circular_change2