CHIP

$\mathrm{𝚌𝚑𝚊𝚗𝚐𝚎}(\mathrm{𝙽𝙲𝙷𝙰𝙽𝙶𝙴},\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝙲𝚃𝚁})$

$\mathrm{𝚗𝚋𝚌𝚑𝚊𝚗𝚐𝚎𝚜}$, $\mathrm{𝚜𝚒𝚖𝚒𝚕𝚊𝚛𝚒𝚝𝚢}$.

In the first example the changes are located between values 4 and 3, 3 and 4, 4 and 1. Consequently, the corresponding $\mathrm{𝚌𝚑𝚊𝚗𝚐𝚎}$ constraint holds since its first argument $\mathrm{𝙽𝙲𝙷𝙰𝙽𝙶𝙴}$ is fixed to value 3.

In the second example the unique change occurs between values 4 and 3. Consequently, the corresponding $\mathrm{𝚌𝚑𝚊𝚗𝚐𝚎}$ constraint holds since its first argument $\mathrm{𝙽𝙲𝙷𝙰𝙽𝙶𝙴}$ is fixed to 1.

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

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.

A similar constraint appears in [PachetRoy99] under the name of $\mathrm{𝚜𝚒𝚖𝚒𝚕𝚊𝚛𝚒𝚝𝚢}$ constraint. The difference consists of replacing the arithmetic constraint $\mathrm{𝙲𝚃𝚁}$ by a binary constraint. When $\mathrm{𝙲𝚃𝚁}$ is equal to $\ne$ this constraint is called $\mathrm{𝚗𝚋𝚌𝚑𝚊𝚗𝚐𝚎𝚜}$ in [Platon03].

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].

$\mathrm{𝚙𝚊𝚝𝚝𝚎𝚛𝚗}$.

common keyword: $\mathrm{𝚌𝚑𝚊𝚗𝚐𝚎}\_\mathrm{𝚙𝚊𝚛𝚝𝚒𝚝𝚒𝚘𝚗}$, $\mathrm{𝚌𝚒𝚛𝚌𝚞𝚕𝚊𝚛}\_\mathrm{𝚌𝚑𝚊𝚗𝚐𝚎}$ (number of changes in a sequence of $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}$ with respect to a $\mathrm{𝚋𝚒𝚗𝚊𝚛𝚢}\mathrm{𝚌𝚘𝚗𝚜𝚝𝚛𝚊𝚒𝚗𝚝}$), $\mathrm{𝚌𝚢𝚌𝚕𝚒𝚌}\_\mathrm{𝚌𝚑𝚊𝚗𝚐𝚎}$, $\mathrm{𝚌𝚢𝚌𝚕𝚒𝚌}\_\mathrm{𝚌𝚑𝚊𝚗𝚐𝚎}\_\mathrm{𝚓𝚘𝚔𝚎𝚛}$ (number of changes), $\mathrm{𝚜𝚖𝚘𝚘𝚝𝚑}$ (number of changes in a sequence of $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}$ with respect to a $\mathrm{𝚋𝚒𝚗𝚊𝚛𝚢}\mathrm{𝚌𝚘𝚗𝚜𝚝𝚛𝚊𝚒𝚗𝚝}$).

generalisation: $\mathrm{𝚌𝚑𝚊𝚗𝚐𝚎}\_\mathrm{𝚙𝚊𝚒𝚛}$ ($\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$ replaced by $\mathrm{𝚙𝚊𝚒𝚛}$ of $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}$).

shift of concept: $\mathrm{𝚍𝚒𝚜𝚝𝚊𝚗𝚌𝚎}\_\mathrm{𝚌𝚑𝚊𝚗𝚐𝚎}$, $\mathrm{𝚕𝚘𝚗𝚐𝚎𝚜𝚝}\_\mathrm{𝚌𝚑𝚊𝚗𝚐𝚎}$.

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.

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

Since we are only interested by the constraints linking two consecutive items of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ we use $\mathrm{𝑃𝐴𝑇𝐻}$ 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 $\mathrm{𝐍𝐀𝐑𝐂}$ graph property, the arcs of the final graph are stressed in bold.

Figure 5.49.1. Initial and final graph of the $\mathrm{𝚌𝚑𝚊𝚗𝚐𝚎}$ constraint

(a)	(b)

Figure 5.49.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 ${\mathrm{𝚅𝙰𝚁}}_i\mathrm{𝙲𝚃𝚁}{\mathrm{𝚅𝙰𝚁}}_{i+1}$ 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$: ${\mathrm{𝚅𝙰𝚁}}_i\mathrm{𝙲𝚃𝚁}{\mathrm{𝚅𝙰𝚁}}_{i+1}\iff {𝚂}_i$.

Figure 5.49.2. Automaton (with counter) of the $\mathrm{𝚌𝚑𝚊𝚗𝚐𝚎}$ constraint

Figure 5.49.3. Hypergraph of the reformulation corresponding to the automaton (with 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$ and $𝒟$ respectively denote the number of variables of the collection $\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 ${\mathrm{𝚅𝙰𝚁}}_i\mathrm{𝙲𝚃𝚁}{\mathrm{𝚅𝙰𝚁}}_{i+1}$ $(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 ${\mathrm{𝚅𝙰𝚁}}_i\mathrm{𝙲𝚃𝚁}{\mathrm{𝚅𝙰𝚁}}_{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\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 \left\{k\right|i\neg \mathrm{𝙲𝚃𝚁}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\mathrm{𝙲𝚃𝚁}k$ does not hold).

4. $\forall i\in 𝒟,\forall j\in [0,m-1],\forall k\in 𝒟\setminus \left\{k\right|i\neg \mathrm{𝙲𝚃𝚁}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\mathrm{𝙲𝚃𝚁}k$ holds).

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.49.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 $\ne$.

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