5.203. longest_change

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

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

Constraint

πš•πš˜πš—πšπšŽπšœπš_πšŒπš‘πšŠπš—πšπšŽ(πš‚π™Έπš‰π™΄,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,π™²πšƒπš)

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

πš‚π™Έπš‰π™΄ is the maximum number of consecutive variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ for which constraint π™²πšƒπš holds in an uninterrupted way. We count a change when X π™²πšƒπš Y holds; X and Y are two consecutive variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

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

The πš•πš˜πš—πšπšŽπšœπš_πšŒπš‘πšŠπš—πšπšŽ constraint holds since its first argument πš‚π™Έπš‰π™΄=4 is fixed to the length of the longest subsequence of consecutive values of the collection 〈8,8,3,4,1,1,5,5,2βŒͺ such that two consecutive values are distinct (i.e.,Β subsequence 8 3 4 1).

Symmetry

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

See also

root concept: πšŒπš‘πšŠπš—πšπšŽ.

Keywords

characteristic of a constraint: automaton, automaton with counters.

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

constraint type: timetabling constraint.

miscellaneous: obscure.

Arc input(s)

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

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

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

Graph model

In order to specify the πš•πš˜πš—πšπšŽπšœπš_πšŒπš‘πšŠπš—πšπšŽ constraint, we use πŒπ€π—_𝐍𝐂𝐂, which is the number of vertices of the largest connected component. Since the initial graph corresponds to a path, this will be the length of the longest path in the final graph.

PartsΒ (A) andΒ (B) of FigureΒ 5.203.1 respectively show the initial and final graph associated with the Example slot. Since we use the πŒπ€π—_𝐍𝐂𝐂 graph property we show the largest connected component of the final graph. It corresponds to the longest period of uninterrupted changes: sequence 8,3,4,1 that involves 4 consecutive variables.

Figure 5.203.1. Initial and final graph of the πš•πš˜πš—πšπšŽπšœπš_πšŒπš‘πšŠπš—πšπšŽ constraint
ctrs/longest_changeActrs/longest_changeB
(a) (b)
Automaton

FigureΒ 5.203.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 π™²πšƒπš πš…π™°πš i+1 β‡”πš‚ i .

Figure 5.203.2. Automaton of the πš•πš˜πš—πšπšŽπšœπš_πšŒπš‘πšŠπš—πšπšŽ constraint
ctrs/longest_change1
Figure 5.203.3. Hypergraph of the reformulation corresponding to the automaton of the πš•πš˜πš—πšπšŽπšœπš_πšŒπš‘πšŠπš—πšπšŽ constraint
ctrs/longest_change2