Derived from $\mathrm{𝚌𝚑𝚊𝚗𝚐𝚎}$.

$\mathrm{𝚜𝚖𝚘𝚘𝚝𝚑}(\mathrm{𝙽𝙲𝙷𝙰𝙽𝙶𝙴},\mathrm{𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴},\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂})$

In the example we have one change between values 5 and 2 since the difference in absolute value is greater than the tolerance (i.e., $|5-2|>2$). Consequently the $\mathrm{𝙽𝙲𝙷𝙰𝙽𝙶𝙴}$ argument is fixed to 1 and the $\mathrm{𝚜𝚖𝚘𝚘𝚝𝚑}$ constraint holds.

• Items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ can be reversed.

• One and the same constant can be added to the $\mathrm{𝚟𝚊𝚛}$ attribute of all items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

This constraint is useful for the following problems:

• Assume that $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ corresponds to the number of people that work on consecutive weeks. One may not normally increase or decrease too drastically the number of people from one week to the next week. With the $\mathrm{𝚜𝚖𝚘𝚘𝚝𝚑}$ constraint you can state a limit on the number of drastic changes.

• Assume you have to produce a set of orders, each order having a specific attribute. You want to generate the orders in such a way that there is not a too big difference between the values of the attributes of two consecutive orders. If you can't achieve this on two given specific orders, this would imply a set-up or a cost. Again, with the $\mathrm{𝚜𝚖𝚘𝚘𝚝𝚑}$ constraint, you can control this kind of drastic changes.

A first incomplete algorithm is described in [BeldiceanuCarlsson01]. The sketch of a filtering algorithm for the conjunction of the $\mathrm{𝚜𝚖𝚘𝚘𝚝𝚑}$ and the $\mathrm{𝚜𝚝𝚛𝚎𝚝𝚌𝚑}$ 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].

common keyword: $\mathrm{𝚌𝚑𝚊𝚗𝚐𝚎}$ (number of changes in a sequence with respect to a binary constraint).

related: $\mathrm{𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎}$.

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

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

constraint type: timetabling constraint.

filtering: dynamic programming, arc-consistency.

modelling: number of changes.

modelling exercises: n-Amazon.

puzzles: n-Amazon.

$\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$

Parts (A) and (B) of Figure 5.298.1 respectively show the initial and final graph associated with the Example slot. Since we use the $\mathrm{𝐍𝐀𝐑𝐂}$ graph property, the unique arc of the final graph is stressed in bold.

Figure 5.298.1. Initial and final graph of the $\mathrm{𝚜𝚖𝚘𝚘𝚝𝚑}$ constraint

(a)	(b)

Figure 5.298.2 depicts a first automaton that only accepts all the solutions of the $\mathrm{𝚜𝚖𝚘𝚘𝚝𝚑}$ constraint. This automaton uses a counter in order to record the number of satisfied constraints of the form $\left(\right|{\mathrm{𝚅𝙰𝚁}}_i-{\mathrm{𝚅𝙰𝚁}}_{i+1}\left|\right)>\mathrm{𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴}$ already encountered. To each pair of consecutive variables $({\mathrm{𝚅𝙰𝚁}}_i,{\mathrm{𝚅𝙰𝚁}}_{i+1})$ of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ corresponds a 0-1 signature variable ${𝚂}_i$. The following signature constraint links ${\mathrm{𝚅𝙰𝚁}}_i$, ${\mathrm{𝚅𝙰𝚁}}_{i+1}$ and ${𝚂}_i$: $\left(\right|{\mathrm{𝚅𝙰𝚁}}_i-{\mathrm{𝚅𝙰𝚁}}_{i+1}\left|\right)>\mathrm{𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴}\iff {𝚂}_i=1$.

Figure 5.298.2. Automaton (with a counter) of the $\mathrm{𝚜𝚖𝚘𝚘𝚝𝚑}$ constraint

Figure 5.298.3. Hypergraph of the reformulation corresponding to the automaton (with a counter) of the $\mathrm{𝚜𝚖𝚘𝚘𝚝𝚑}$ constraint

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 $\mathrm{𝚜𝚖𝚘𝚘𝚝𝚑}$ constraint. Without loss of generality, assume that the collection of variables $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ contains at least two variables (i.e., $\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right|\ge 2$). Let $n$, $\mathrm{𝑚𝑖𝑛}$, $\mathrm{𝑚𝑎𝑥}$, and $𝒟$ respectively denote the number of variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$, the smallest value that can be assigned to the variables of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$, the largest value that can be assigned to the variables of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$, and the union of the domains of the variables of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$. Clearly, the maximum number of changes (i.e., the number of times the constraint $\left(\right|{\mathrm{𝚅𝙰𝚁}}_i-{\mathrm{𝚅𝙰𝚁}}_{i+1}\left|\right)>\mathrm{𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴}$ $(1\le i<n)$ holds) cannot exceed the quantity $m=min(n-1,\overline{\mathrm{𝙽𝙲𝙷𝙰𝙽𝙶𝙴}})$. The $(m+1)·\left|𝒟\right|+2$ states of the automaton that only accepts all the solutions of the $\mathrm{𝚜𝚖𝚘𝚘𝚝𝚑}$ constraint are defined in the following way:

• We have an initial state labelled by $s_I$.

• We have $m·\left|𝒟\right|$ intermediate states labelled by $s_{ij}$ $(i\in 𝒟,j\in [0,m\left]\right)$. 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 $\left(\right|{\mathrm{𝚅𝙰𝚁}}_k-{\mathrm{𝚅𝙰𝚁}}_{k+1}\left|\right)>\mathrm{𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴}$ 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\in 𝒟)$.

2. There is a transition, labelled by $j$, from every state $s_{ij}$, $(i\in 𝒟,j\in [0,m\left]\right)$, to the final state $s_F$.

3. $\forall i\in 𝒟,\forall j\in [0,m],\forall k\in 𝒟\cap [max(\mathrm{𝑚𝑖𝑛},i-\mathrm{𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴}),min(\mathrm{𝑚𝑎𝑥},i+\mathrm{𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴}\left)\right]$ there is a transition labelled by $k$ from $s_{ij}$ to $s_{kj}$ (i.e., the counter $j$ does not change for values $k$ that are too closed from value $i$).

4. $\forall i\in 𝒟,\forall j\in [0,m-1],\forall k\in 𝒟\setminus [max(\mathrm{𝑚𝑖𝑛},i-\mathrm{𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴}),min(\mathrm{𝑚𝑎𝑥},i+\mathrm{𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴}\left)\right]$ 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$ that are too far from $i$).

We have $\left|𝒟\right|$ transitions of type 1, $\left|𝒟\right|·(m+1)$ transitions of type 2, and at least ${\left|𝒟\right|}^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 ${\left|𝒟\right|}^2·(n-1)$ transitions. This leads to a worst case time complexity of $O\left(\right|𝒟{|}^2·n^2)$ if we use Pesant's algorithm for filtering the $\mathrm{𝚛𝚎𝚐𝚞𝚕𝚊𝚛}$ constraint [Pesant04].

Figure 5.298.4 depicts the corresponding counter free non deterministic automaton associated with the $\mathrm{𝚜𝚖𝚘𝚘𝚝𝚑}$ constraint under the hypothesis that (1) all variables of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ are assigned a value in $\{0,1,2,3\}$, (2) $\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right|$ is equal to 4, and (3) $\mathrm{𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴}$ is equal to 1.

Figure 5.298.4. Counter free non deterministic automaton of the $\mathrm{𝚜𝚖𝚘𝚘𝚝𝚑}$$(\mathrm{𝙽𝙲𝙷𝙰𝙽𝙶𝙴},1,\langle {\mathrm{𝚅𝙰𝚁}}_1,{\mathrm{𝚅𝙰𝚁}}_2,{\mathrm{𝚅𝙰𝚁}}_3,{\mathrm{𝚅𝙰𝚁}}_4\rangle )$ constraint assuming ${\mathrm{𝚅𝙰𝚁}}_i\in [0,3]$ $(1\le i\le 3)$, with initial state $s_I$ and final state $s_F$