## 5.161. increasing_nvalue

Origin
Constraint

$\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }\left(\mathrm{\pi ½\pi  \pi °\pi »},\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$

Arguments
 $\mathrm{\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)$
Restrictions
 $\mathrm{\pi ½\pi  \pi °\pi »}\beta ₯\mathrm{\pi \pi \pi }\left(1,|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|\right)$ $\mathrm{\pi ½\pi  \pi °\pi »}\beta €|\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)$ $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$$\left(\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }\right)$
Purpose

The variables of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ are increasing. In addition, $\mathrm{\pi ½\pi  \pi °\pi »}$ is the number of distinct values taken by the variables of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$.

Example
$\left(2,β©6,6,8,8,8βͺ\right)$

The $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$ constraint (see FigureΒ 5.161.1 for a graphical representation) holds since:

• The values of the collection $\beta ©6,6,8,8,8\beta ͺ$ are sorted in increasing order.

• $\mathrm{\pi ½\pi  \pi °\pi »}=2$ is set to the number of distinct values occurring within the collection $\beta ©6,6,8,8,8\beta ͺ$.

Typical
 $|\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 }$.

Algorithm

A complete filtering algorithm in a linear time complexity over the sum of the domain sizes is described inΒ [BeldiceanuHermenierLorcaPetit10]. A generalisation of this algorithm to other constraints is given inΒ [BeldiceanuLorcaPetit10].

Reformulation

The $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$ constraint can be expressed in term of a conjunction of a $\mathrm{\pi \pi \pi \pi \pi \pi }$ and an $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraints (i.e.,Β a chain of non strict inequality constraints on adjacent variables of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$). But as shown by the following example, ${V}_{1}\beta \left[1,2\right]$, ${V}_{2}\beta \left[1,2\right]$, ${V}_{1}\beta €{V}_{2}$, $\mathrm{\pi \pi \pi \pi \pi \pi }$($2,\beta ©{V}_{1},{V}_{2}\beta ͺ$), this hinders propagation (i.e.,Β the unique solution ${V}_{1}=1$, ${V}_{2}=2$ is not directly obtained after stating all the previous constraints).

Systems

implies: $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$Β (remove $\mathrm{\pi ½\pi  \pi °\pi »}$ parameter from $\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 }$.

shift of concept: $\mathrm{\pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi }$Β ($\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }$ replaced by $\mathrm{\pi \pi \pi \pi \pi \pi }$ and $\beta €$ replaced by $\mathrm{\pi \pi \pi ‘}_\mathrm{\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 \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 \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 »}$

Graph class
$\mathrm{\pi ΄\pi \pi \pi Έ\pi  \pi °\pi »\pi ΄\pi ½\pi ²\pi ΄}$

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.161.2 respectively show the initial and final graph associated with the Example slot. Since we use the $\mathrm{\pi \pi \pi \pi }$ graph property we show the different strongly connected components of the final graph. Each strongly connected component corresponds to a value that is assigned to some variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection. The 2 following values 6 and 8 are used by the variables of the $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ collection.

Automaton

A first systematic approach for creating an automaton that only recognises the solutions of the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$ constraint could be to:

However this approach is not going to scale well in practice since the automaton associated with the $\mathrm{\pi \pi \pi \pi \pi \pi }$ constraint has a too big size. Therefore we propose an approach where we directly construct in one single step the automaton that only recognises the solutions of the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$ constraint. Note that we do not have any formal proof that the resulting automaton is always minimum.

Without loss of generality, assume that the collection of variables $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ contains at least one variable (i.e.,Β $|\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }|\beta ₯1$). Let $l$, $m$, $n$, $\mathrm{\pi \pi \pi }$ and $\mathrm{\pi \pi \pi ₯}$ respectively denote the minimum and maximum possible value of variable $\mathrm{\pi ½\pi  \pi °\pi »}$, the number of variables of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$, the smallest value that can be assigned to the variables of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$, and the largest value that can be assigned to the variables of $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$. Let $s=\mathrm{\pi \pi \pi ₯}-\mathrm{\pi \pi \pi }+1$ denote the total number of potential values. Clearly, the maximum number of distinct values that can be assigned to the variables of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ cannot exceed the quantity $d=min\left(m,n,s\right)$. The $\frac{sΒ·\left(s+1\right)}{2}-\frac{\left(s-d\right)Β·\left(s-d+1\right)}{2}+1$ states of the automaton that only accepts solutions of the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$ constraint can be defined in the following way:

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

• We have $\frac{sΒ·\left(s+1\right)}{2}-\frac{\left(s-d\right)Β·\left(s-d+1\right)}{2}$ states labelled by ${s}_{ij}$ $\left(1\beta €i\beta €d,i\beta €j\beta €s\right)$. The first index $i$ of a state ${s}_{ij}$ corresponds to the number of distinct values already encountered, while the second index $j$ denotes the the current value (i.e.,Β more precisely the index of the current value, where the minimum value has index 1).

Terminal states depend on the possible values of variable $\mathrm{\pi ½\pi  \pi °\pi »}$ and correspond to those states ${s}_{ij}$ such that $i$ is a possible value for variable $\mathrm{\pi ½\pi  \pi °\pi »}$. Note that we assume no further restriction on the domain of $\mathrm{\pi ½\pi  \pi °\pi »}$ (otherwise the set of terminal states needs to be reduced in order to reflect the current set of possible values of $\mathrm{\pi ½\pi  \pi °\pi »}$). Three classes of transitions are respectively defined in the following way:

1. There is a transition, labelled by $\mathrm{\pi \pi \pi }+j-1$, from the initial state ${s}_{00}$ to the state ${s}_{1j}$ $\left(1\beta €j\beta €s\right)$.

2. There is a loop, labelled by $\mathrm{\pi \pi \pi }+j-1$ for every state ${s}_{ij}$ $\left(1\beta €i\beta €d,i\beta €j\beta €s\right)$.

3. $\beta i\beta \left[1,d-1\right],\beta j\beta \left[i,s\right],\beta k\beta \left[j+1,s\right]$ there is a transition labelled by $\mathrm{\pi \pi \pi }+k-1$ from ${s}_{ij}$ to ${s}_{i+1k}$.

We respectively have $s$ transitions of class 1, $\frac{sΒ·\left(s+1\right)}{2}-\frac{\left(s-d\right)Β·\left(s-d+1\right)}{2}$ transitions of class 2, and $\frac{\left(s-1\right)Β·sΒ·\left(s+1\right)}{6}-\frac{\left(s-d\right)Β·\left(s-d+1\right)Β·\left(s-d+2\right)}{6}$ transitions of class 3.

Note that all states ${s}_{ij}$ such that $i+s-j can be discarded since they do not allow to reach the minimum number of distinct values required $l$.

PartΒ (A) of FigureΒ 5.161.3 depicts the automaton associated with the $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi }$ constraint of the Example slot. For this purpose, we assume that variable $\mathrm{\pi ½\pi  \pi °\pi »}$ is fixed to value 2 and that variables of the collection $\mathrm{\pi  \pi °\pi \pi Έ\pi °\pi ±\pi »\pi ΄\pi }$ take their values within interval $\left[6,8\right]$. PartΒ (B) of FigureΒ 5.161.3 represents the simplified automaton where all states that do not allow to reach a terminal state were removed. The $\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 \pi \pi \pi \pi \pi ’}$ constraint holds since the corresponding sequence of visited states, ${s}_{00}$ ${s}_{11}$ ${s}_{11}$ ${s}_{23}$ ${s}_{23}$ ${s}_{23}$, ends up in a terminal state (i.e.,Β terminal states are depicted by thick circles in the figure).