5.49. change

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

CHIP

Constraint

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

Synonyms

πš—πš‹πšŒπš‘πšŠπš—πšπšŽπšœ, πšœπš’πš–πš’πš•πšŠπš›πš’πšπš’.

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

𝙽𝙲𝙷𝙰𝙽𝙢𝙴 is the number of times that constraint π™²πšƒπš holds on consecutive variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

Example
(3,4,4,3,4,1,β‰ )
(1,1,2,4,3,7,>)

In the first example the changes are located between values 4 and 3, 3 and 4, 4 and 1. Consequently, the corresponding πšŒπš‘πšŠπš—πšπšŽ constraint holds since its first argument 𝙽𝙲𝙷𝙰𝙽𝙢𝙴 is fixed to value 3.

In the second example the unique change occurs between values 4 and 3. Consequently, the corresponding πšŒπš‘πšŠπš—πšπšŽ constraint holds since its first argument 𝙽𝙲𝙷𝙰𝙽𝙢𝙴 is fixed to 1.

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

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

Usage

This constraint can be used in the context of timetabling problems in order to put an upper limit on the number of changes of job types during a given period.

Remark

A similar constraint appears inΒ [PachetRoy99] under the name of πšœπš’πš–πš’πš•πšŠπš›πš’πšπš’ constraint. The difference consists of replacing the arithmetic constraint π™²πšƒπš by a binary constraint. When π™²πšƒπš is equal to β‰  this constraint is called πš—πš‹πšŒπš‘πšŠπš—πšπšŽπšœ in [Platon03].

Algorithm

A first incomplete algorithm is described inΒ [BeldiceanuCarlsson01]. The sketch of a filtering algorithm for the conjunction of the πšŒπš‘πšŠπš—πšπšŽ and the πšœπšπš›πšŽπšπšŒπš‘ constraints based on dynamic programming achieving arc -consistency is mentioned by LarsΒ Hellsten inΒ [Hellsten04]. An arc -consistency algorithm in linear time of the sum of domain sizes is described inΒ [BeldiceanuLorcaPetit10].

Used in

πš™πšŠπšπšπšŽπš›πš—.

See also

common keyword: πšŒπš‘πšŠπš—πšπšŽ_πš™πšŠπš›πšπš’πšπš’πš˜πš—, πšŒπš’πš›πšŒπšžπš•πšŠπš›_πšŒπš‘πšŠπš—πšπšŽΒ (number of changes in a sequence of πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ with respect to a πš‹πš’πš—πšŠπš›πš’ πšŒπš˜πš—πšœπšπš›πšŠπš’πš—πš), πšŒπš’πšŒπš•πš’πšŒ_πšŒπš‘πšŠπš—πšπšŽ, πšŒπš’πšŒπš•πš’πšŒ_πšŒπš‘πšŠπš—πšπšŽ_πš“πš˜πš”πšŽπš›Β (number of changes), πšœπš–πš˜πš˜πšπš‘Β (number of changes in a sequence of πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ with respect to a πš‹πš’πš—πšŠπš›πš’ πšŒπš˜πš—πšœπšπš›πšŠπš’πš—πš).

generalisation: πšŒπš‘πšŠπš—πšπšŽ_πš™πšŠπš’πš›Β (πšŸπšŠπš›πš’πšŠπš‹πš•πšŽ replaced by πš™πšŠπš’πš› of πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ).

shift of concept: πšπš’πšœπšπšŠπš—πšŒπšŽ_πšŒπš‘πšŠπš—πšπšŽ, πš•πš˜πš—πšπšŽπšœπš_πšŒπš‘πšŠπš—πšπšŽ.

Keywords

characteristic of a constraint: automaton, automaton with counters, non-deterministic automaton.

constraint network structure: sliding cyclic(1) constraint network(2), sliding cyclic(1) constraint network(3), Berge-acyclic constraint network.

constraint type: timetabling constraint.

filtering: dynamic programming, arc-consistency.

final graph structure: acyclic, bipartite, no loop.

modelling: number of changes.

Arc input(s)

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

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

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

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

Graph model

Since we are only interested by the constraints linking two consecutive items of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ we use 𝑃𝐴𝑇𝐻 to generate the arcs of the initial graph.

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

Figure 5.49.1. Initial and final graph of the πšŒπš‘πšŠπš—πšπšŽ constraint
ctrs/changeActrs/changeB
(a) (b)
Automaton

FigureΒ 5.49.2 depicts a first automaton that only accepts all the solutions of the πšŒπš‘πšŠπš—πšπšŽ constraint. This automaton uses a counter in order to record the number of satisfied constraints of the form πš…π™°πš i π™²πšƒπš πš…π™°πš i+1 already encountered. 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 π™²πšƒπš πš…π™°πš i+1 β‡”πš‚ i .

Figure 5.49.2. Automaton (with counter) of the πšŒπš‘πšŠπš—πšπšŽ constraint
ctrs/change1
Figure 5.49.3. Hypergraph of the reformulation corresponding to the automaton (with counter) of the πšŒπš‘πšŠπš—πšπšŽ constraint
ctrs/change2

Since the reformulation associated with the previous automaton is not Berge-acyclic, we now describe a second counter free automaton that also only accepts all the solutions of the πšŒπš‘πšŠπš—πšπšŽ constraint. Without loss of generality, assume that the collection of variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ contains at least two variables (i.e.,Β |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|β‰₯2). Let n and π’Ÿ respectively denote the number of variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚, and the union of the domains of the variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚. Clearly, the maximum number of changes (i.e.,Β the number of times the constraint πš…π™°πš i π™²πšƒπš πš…π™°πš i+1 (1≀i<n) holds) cannot exceed the quantity m=min(n-1,𝙽𝙲𝙷𝙰𝙽𝙢𝙴 Β―). The (m+1)Β·|π’Ÿ|+2 states of the automaton that only accepts all the solutions of the πšŒπš‘πšŠπš—πšπšŽ constraint are defined in the following way:

  • We have an initial state labelled by s I .

  • We have mΒ·|π’Ÿ| intermediate states labelled by s ij (iβˆˆπ’Ÿ,j∈[0,m]). The first subscript i of state s ij corresponds to the value currently encountered. The second subscript j denotes the number of already encountered satisfied constraints of the form πš…π™°πš i π™²πšƒπš πš…π™°πš i+1 from the initial state s I to the state s ij .

  • We have a final state labelled by s F .

Four classes of transitions are respectively defined in the following way:

  1. There is a transition, labelled by i from the initial state s I to the state s i0 , (iβˆˆπ’Ÿ).

  2. There is a transition, labelled by j, from every state s ij , (iβˆˆπ’Ÿ,j∈[0,m]), to the final state s F .

  3. βˆ€iβˆˆπ’Ÿ, βˆ€j∈[0,m], βˆ€kβˆˆπ’Ÿβˆ©{k | i Β¬ π™²πšƒπš k} there is a transition labelled by k from s ij to s kj (i.e.,Β the counter j does not change for values k such that constraint i π™²πšƒπš k does not hold).

  4. βˆ€iβˆˆπ’Ÿ, βˆ€j∈[0,m-1], βˆ€kβˆˆπ’Ÿβˆ–{k | i Β¬ π™²πšƒπš k} there is a transition labelled by k from s ij to s kj+1 (i.e.,Β the counter j is incremented by +1 for values k such that constraint i π™²πšƒπš k holds).

We have |π’Ÿ| transitions of typeΒ 1, |π’Ÿ|Β·(m+1) transitions of typeΒ 2, and at least |π’Ÿ| 2 Β·m transitions of typesΒ 3 and 4. Since the maximum value of m is equal to n-1, in the worst case we have at least |π’Ÿ| 2 Β·(n-1) transitions. This leads to a worst case time complexity of O(|π’Ÿ| 2 Β·n 2 ) if we use Pesant's algorithm for filtering the πš›πšŽπšπšžπš•πšŠπš› constraintΒ [Pesant04].

FigureΒ 5.49.4 depicts the corresponding counter free non deterministic automaton associated with the πšŒπš‘πšŠπš—πšπšŽ constraint under the hypothesis that (1)Β all variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are assigned a value in {0,1,2,3}, (2)Β |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚| is equal to 4, and (3)Β  π™²πšƒπš is equal to β‰ .

Figure 5.49.4. Counter free non deterministic automaton of the πšŒπš‘πšŠπš—πšπšŽ(𝙽𝙲𝙷𝙰𝙽𝙢𝙴,βŒ©πš…π™°πš 1 ,πš…π™°πš 2 ,πš…π™°πš 3 ,πš…π™°πš 4 βŒͺ,β‰ ) constraint assuming πš…π™°πš i ∈[0,3] (1≀i≀3), with initial state s I and final state s F
ctrs/change3