5.49. change

Origin

CHIP

Constraint

$\mathrm{\pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi ½\pi ²\pi ·\pi °\pi ½\pi Ά\pi ΄},\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi ²\pi \pi }\right)$

Synonyms

$\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi ’}$.

Arguments
 $\mathrm{\pi ½\pi ²\pi ·\pi °\pi ½\pi Ά\pi ΄}$ $\mathrm{\pi \pi \pi \pi }$ $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi }-\mathrm{\pi \pi \pi \pi }\right)$ $\mathrm{\pi ²\pi \pi }$ $\mathrm{\pi \pi \pi \pi }$
Restrictions
 $\mathrm{\pi ½\pi ²\pi ·\pi °\pi ½\pi Ά\pi ΄}\beta ₯0$ $\mathrm{\pi ½\pi ²\pi ·\pi °\pi ½\pi Ά\pi ΄}<|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi },\mathrm{\pi \pi \pi }\right)$
Purpose

$\mathrm{\pi ½\pi ²\pi ·\pi °\pi ½\pi Ά\pi ΄}$ is the number of times that constraint $\mathrm{\pi ²\pi \pi }$ holds on consecutive variables of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$.

Example
 $\left(1,β©1,2,4,3,7βͺ,>\right)$

In the first example the changes are located between values 4 and 3, 3 and 4, 4 and 1. Consequently, the corresponding $\mathrm{\pi \pi \pi \pi \pi \pi }$ constraint holds since its first argument $\mathrm{\pi ½\pi ²\pi ·\pi °\pi ½\pi Ά\pi ΄}$ is fixed to value 3.

In the second example the unique change occurs between values 4 and 3. Consequently, the corresponding $\mathrm{\pi \pi \pi \pi \pi \pi }$ constraint holds since its first argument $\mathrm{\pi ½\pi ²\pi ·\pi °\pi ½\pi Ά\pi ΄}$ is fixed to 1.

Typical
 $\mathrm{\pi ½\pi ²\pi ·\pi °\pi ½\pi Ά\pi ΄}>0$ $|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|>1$ $\mathrm{\pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }.\mathrm{\pi \pi \pi }\right)>1$
Symmetry

One and the same constant can be added to the $\mathrm{\pi \pi \pi }$ attribute of all items of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$.

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 $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi ’}$ constraint. The difference consists of replacing the arithmetic constraint $\mathrm{\pi ²\pi \pi }$ by a binary constraint. When $\mathrm{\pi ²\pi \pi }$ is equal to this constraint is called $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }$ in [Platon03].

Algorithm

A first incomplete algorithm is described inΒ [BeldiceanuCarlsson01]. The sketch of a filtering algorithm for the conjunction of the $\mathrm{\pi \pi \pi \pi \pi \pi }$ and the $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ 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

common keyword: $\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$Β (number of changes in a sequence of $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }$ with respect to a $\mathrm{\pi \pi \pi \pi \pi \pi ’}\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$), $\mathrm{\pi \pi ’\pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$, $\mathrm{\pi \pi ’\pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }$Β (number of changes), $\mathrm{\pi \pi \pi \pi \pi \pi }$Β (number of changes in a sequence of $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }$ with respect to a $\mathrm{\pi \pi \pi \pi \pi \pi ’}\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$).

generalisation: $\mathrm{\pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$Β ($\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ replaced by $\mathrm{\pi \pi \pi \pi }$ of $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }$).

Keywords
Arc input(s)

$\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$

Arc generator
$\mathrm{\pi \pi ΄\pi \pi »}$$\beta ¦\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1},\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}\right)$

Arc arity
Arc constraint(s)
$\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{1}.\mathrm{\pi \pi \pi }\mathrm{\pi ²\pi \pi }\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi }\mathtt{2}.\mathrm{\pi \pi \pi }$
Graph property(ies)
$\mathrm{\pi \pi \pi \pi }$$=\mathrm{\pi ½\pi ²\pi ·\pi °\pi ½\pi Ά\pi ΄}$

Graph class
 $\beta ’$$\mathrm{\pi °\pi ²\pi \pi ²\pi »\pi Έ\pi ²}$ $\beta ’$$\mathrm{\pi ±\pi Έ\pi Ώ\pi °\pi \pi \pi Έ\pi \pi ΄}$ $\beta ’$$\mathrm{\pi ½\pi Ύ}_\mathrm{\pi »\pi Ύ\pi Ύ\pi Ώ}$

Graph model

Since we are only interested by the constraints linking two consecutive items of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ we use $\mathrm{\pi \pi ΄\pi \pi »}$ 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{\pi \pi \pi \pi }$ graph property, the arcs of the final graph are stressed in bold.

Automaton

FigureΒ 5.49.2 depicts a first automaton that only accepts all the solutions of the $\mathrm{\pi \pi \pi \pi \pi \pi }$ constraint. This automaton uses a counter in order to record the number of satisfied constraints of the form ${\mathrm{\pi  \pi °\pi }}_{i}\mathrm{\pi ²\pi \pi }{\mathrm{\pi  \pi °\pi }}_{i+1}$ already encountered. To each pair of consecutive variables $\left({\mathrm{\pi  \pi °\pi }}_{i},{\mathrm{\pi  \pi °\pi }}_{i+1}\right)$ of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ corresponds a 0 -1 signature variable ${\mathrm{\pi }}_{i}$. The following signature constraint links ${\mathrm{\pi  \pi °\pi }}_{i}$, ${\mathrm{\pi  \pi °\pi }}_{i+1}$ and ${\mathrm{\pi }}_{i}$: ${\mathrm{\pi  \pi °\pi }}_{i}\mathrm{\pi ²\pi \pi }{\mathrm{\pi  \pi °\pi }}_{i+1}\beta {\mathrm{\pi }}_{i}$.

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{\pi \pi \pi \pi \pi \pi }$ constraint. Without loss of generality, assume that the collection of variables $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ contains at least two variables (i.e.,Β $|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|\beta ₯2$). Let $n$ and $\mathrm{\pi }$ respectively denote the number of variables of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$, and the union of the domains of the variables of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$. Clearly, the maximum number of changes (i.e.,Β the number of times the constraint ${\mathrm{\pi  \pi °\pi }}_{i}\mathrm{\pi ²\pi \pi }{\mathrm{\pi  \pi °\pi }}_{i+1}$ $\left(1\beta €i holds) cannot exceed the quantity $m=min\left(n-1,\stackrel{Β―}{\mathrm{\pi ½\pi ²\pi ·\pi °\pi ½\pi Ά\pi ΄}}\right)$. The $\left(m+1\right)Β·|\mathrm{\pi }|+2$ states of the automaton that only accepts all the solutions of the $\mathrm{\pi \pi \pi \pi \pi \pi }$ constraint are defined in the following way:

• We have an initial state labelled by ${s}_{I}$.

• We have $mΒ·|\mathrm{\pi }|$ intermediate states labelled by ${s}_{ij}$ $\left(i\beta \mathrm{\pi },j\beta \left[0,m\right]\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{\pi  \pi °\pi }}_{i}\mathrm{\pi ²\pi \pi }{\mathrm{\pi  \pi °\pi }}_{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}$, $\left(i\beta \mathrm{\pi }\right)$.

2. There is a transition, labelled by $j$, from every state ${s}_{ij}$, $\left(i\beta \mathrm{\pi },j\beta \left[0,m\right]\right)$, to the final state ${s}_{F}$.

3. $\beta i\beta \mathrm{\pi },\beta j\beta \left[0,m\right],\beta k\beta \mathrm{\pi }\beta ©\left\{k|iΒ¬\mathrm{\pi ²\pi \pi }k\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$ such that constraint $i\mathrm{\pi ²\pi \pi }k$ does not hold).

4. $\beta i\beta \mathrm{\pi },\beta j\beta \left[0,m-1\right],\beta k\beta \mathrm{\pi }\beta \left\{k|iΒ¬\mathrm{\pi ²\pi \pi }k\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$ such that constraint $i\mathrm{\pi ²\pi \pi }k$ holds).

We have $|\mathrm{\pi }|$ transitions of typeΒ 1, $|\mathrm{\pi }|Β·\left(m+1\right)$ transitions of typeΒ 2, and at least ${|\mathrm{\pi }|}^{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 ${|\mathrm{\pi }|}^{2}Β·\left(n-1\right)$ transitions. This leads to a worst case time complexity of $O\left(|\mathrm{\pi }{|}^{2}Β·{n}^{2}\right)$ if we use Pesant's algorithm for filtering the $\mathrm{\pi \pi \pi \pi \pi \pi \pi }$ constraintΒ [Pesant04].

FigureΒ 5.49.4 depicts the corresponding counter free non deterministic automaton associated with the $\mathrm{\pi \pi \pi \pi \pi \pi }$ constraint under the hypothesis that (1)Β all variables of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ are assigned a value in $\left\{0,1,2,3\right\}$, (2)Β $|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|$ is equal to 4, and (3)Β $\mathrm{\pi ²\pi \pi }$ is equal to .