5.93. cyclic_change

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

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

Constraint

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

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

𝙽𝙲𝙷𝙰𝙽𝙢𝙴 is the number of times that constraint ((X+1) mod π™²πšˆπ™²π™»π™΄_π™»π™΄π™½π™Άπšƒπ™·) π™²πšƒπš Y holds; X and Y correspond to consecutive variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

Example
2,4,3,0,2,3,1,β‰ 

Since π™²πšƒπš is set to β‰  and since π™²πšˆπ™²π™»π™΄_π™»π™΄π™½π™Άπšƒπ™· is set to 4, a change between two consecutive items X and Y of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection corresponds to the fact that the condition ((X+1) mod 4)β‰ Y holds. Consequently, the πšŒπš’πšŒπš•πš’πšŒ_πšŒπš‘πšŠπš—πšπšŽ constraint holds since we have the two following changes (i.e., 𝙽𝙲𝙷𝙰𝙽𝙢𝙴=2) within 〈3,0,2,3,1βŒͺ:

  • A first change between the consecutive values 0 and 2,

  • A second change between the consecutive values 3 and 1.

However, the sequence 3 0 does not correspond to a change since (3+1) mod 4 is equal to 0.

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

Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ can be shifted.

Usage

This constraint may be used for personnel cyclic timetabling problems where each person has to work according to cycles. In this context each variable of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection corresponds to the type of work a person performs on a specific day. Because of some perturbation (e.g.,Β illness, unavailability, variation of the workload) it is in practice not reasonable to ask for perfect cyclic solutions. One alternative is to use the πšŒπš’πšŒπš•πš’πšŒ_πšŒπš‘πšŠπš—πšπšŽ constraint and to ask for solutions where one tries to minimise the number of cycle breaks (i.e.,Β the variable 𝙽𝙲𝙷𝙰𝙽𝙢𝙴).

See also

common keyword: πšŒπš‘πšŠπš—πšπšŽ, πšŒπš’πšŒπš•πš’πšŒ_πšŒπš‘πšŠπš—πšπšŽ_πš“πš˜πš”πšŽπš›Β (number of changes).

Keywords

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

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

constraint type: timetabling constraint.

final graph structure: acyclic, bipartite, no loop.

modelling: number of changes.

Arc input(s)

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

Arc generator
π‘ƒπ΄π‘‡π»β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

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

Graph class
β€’ π™°π™²πšˆπ™²π™»π™Έπ™²
β€’ π™±π™Έπ™Ώπ™°πšπšƒπ™Έπšƒπ™΄
β€’ 𝙽𝙾_𝙻𝙾𝙾𝙿

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.93.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.93.1. Initial and final graph of the πšŒπš’πšŒπš•πš’πšŒ_πšŒπš‘πšŠπš—πšπšŽ constraint
ctrs/cyclic_changeActrs/cyclic_changeB
(a) (b)
Automaton

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

Figure 5.93.2. Automaton of the πšŒπš’πšŒπš•πš’πšŒ_πšŒπš‘πšŠπš—πšπšŽ constraint
ctrs/cyclic_change1
Figure 5.93.3. Hypergraph of the reformulation corresponding to the automaton of the πšŒπš’πšŒπš•πš’πšŒ_πšŒπš‘πšŠπš—πšπšŽ constraint
ctrs/cyclic_change2