5.94. cyclic_change_joker

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

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

Constraint

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

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

𝙽𝙲𝙷𝙰𝙽𝙢𝙴 is the number of times that the following constraint holds:

((X+1) mod π™²πšˆπ™²π™»π™΄_π™»π™΄π™½π™Άπšƒπ™·) π™²πšƒπš Y∧X<π™²πšˆπ™²π™»π™΄_π™»π™΄π™½π™Άπšƒπ™·βˆ§Y<π™²πšˆπ™²π™»π™΄_π™»π™΄π™½π™Άπšƒπ™·

X and Y correspond to consecutive variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

Example
2,4,πšŸπšŠπš›-3,πšŸπšŠπš›-0,πšŸπšŠπš›-2,πšŸπšŠπš›-4,πšŸπšŠπš›-4,πšŸπšŠπš›-4,πšŸπšŠπš›-3,πšŸπšŠπš›-1,πšŸπšŠπš›-4,β‰ 

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∧X<4∧Y<4 holds. Consequently, the πšŒπš’πšŒπš•πš’πšŒ_πšŒπš‘πšŠπš—πšπšŽ_πš“πš˜πš”πšŽπš› constraint holds since we have the two following changes (i.e., 𝙽𝙲𝙷𝙰𝙽𝙢𝙴=2) within 〈3,0,2,4,4,4,3,1,4βŒͺ:

  • A first change between 0 and 2,

  • A second change between 3 and 1.

But when the joker value 4 is involved, there is no change. This is why no change is counted between values 2 and 4, between 4 and 4 and between 1 and 4.

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

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

Usage

The πšŒπš’πšŒπš•πš’πšŒ_πšŒπš‘πšŠπš—πšπšŽ_πš“πš˜πš”πšŽπš› constraint can be used in the same context as the πšŒπš’πšŒπš•πš’πšŒ_πšŒπš‘πšŠπš—πšπšŽ constraint with the additional feature: in our example codes 0 to 3 correspond to different type of activities (i.e.,Β working the morning, the afternoon or the night) and code 4 represents a holiday. We want to express the fact that we do not count any change for two consecutive days d 1 , d 2 such that d 1 or d 2 is a holiday.

See also

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

Keywords

characteristic of a constraint: cyclic, joker value, 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.πšŸπšŠπš›
β€’ πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›<π™²πšˆπ™²π™»π™΄_π™»π™΄π™½π™Άπšƒπ™·
β€’ πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›<π™²πšˆπ™²π™»π™΄_π™»π™΄π™½π™Άπšƒπ™·
Graph property(ies)
𝐍𝐀𝐑𝐂=𝙽𝙲𝙷𝙰𝙽𝙢𝙴

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

Graph model

The joker values are those values that are greater than or equal to π™²πšˆπ™²π™»π™΄_π™»π™΄π™½π™Άπšƒπ™·. We do not count any change for those arc constraints involving at least one variable taking a joker value.

PartsΒ (A) andΒ (B) of FigureΒ 5.94.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.94.1. Initial and final graph of the πšŒπš’πšŒπš•πš’πšŒ_πšŒπš‘πšŠπš—πšπšŽ_πš“πš˜πš”πšŽπš› constraint
ctrs/cyclic_change_jokerActrs/cyclic_change_jokerB
(a) (b)
Automaton

FigureΒ 5.94.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 <π™²πšˆπ™²π™»π™΄_π™»π™΄π™½π™Άπšƒπ™·) ∧ (πš…π™°πš i+1 <π™²πšˆπ™²π™»π™΄_π™»π™΄π™½π™Άπšƒπ™·))β‡”πš‚ i .

Figure 5.94.2. Automaton of the πšŒπš’πšŒπš•πš’πšŒ_πšŒπš‘πšŠπš—πšπšŽ_πš“πš˜πš”πšŽπš› constraint
ctrs/cyclic_change_joker1
Figure 5.94.3. Hypergraph of the reformulation corresponding to the automaton of the πšŒπš’πšŒπš•πš’πšŒ_πšŒπš‘πšŠπš—πšπšŽ_πš“πš˜πš”πšŽπš› constraint
ctrs/cyclic_change_joker2