## 5.161. increasing_nvalue

Origin
Constraint

$\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}_\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}\left(\mathrm{𝙽𝚅𝙰𝙻},\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$

Arguments
 $\mathrm{𝙽𝚅𝙰𝙻}$ $\mathrm{𝚍𝚟𝚊𝚛}$ $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$
Restrictions
 $\mathrm{𝙽𝚅𝙰𝙻}\ge \mathrm{𝚖𝚒𝚗}\left(1,|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|\right)$ $\mathrm{𝙽𝚅𝙰𝙻}\le |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚟𝚊𝚛}\right)$ $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$
Purpose

The variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ are increasing. In addition, $\mathrm{𝙽𝚅𝙰𝙻}$ is the number of distinct values taken by the variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

Example
$\left(2,〈6,6,8,8,8〉\right)$

The $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}_\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$ constraint (see Figure 5.161.1 for a graphical representation) holds since:

• The values of the collection $〈6,6,8,8,8〉$ are sorted in increasing order.

• $\mathrm{𝙽𝚅𝙰𝙻}=2$ is set to the number of distinct values occurring within the collection $〈6,6,8,8,8〉$.

Typical
 $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>1$ $\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}\right)>1$
Symmetry

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

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{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}_\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$ constraint can be expressed in term of a conjunction of a $\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$ and an $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}$ constraints (i.e., a chain of non strict inequality constraints on adjacent variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$). But as shown by the following example, ${V}_{1}\in \left[1,2\right]$, ${V}_{2}\in \left[1,2\right]$, ${V}_{1}\le {V}_{2}$, $\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$($2,〈{V}_{1},{V}_{2}〉$), 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{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}$ (remove $\mathrm{𝙽𝚅𝙰𝙻}$ parameter from $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}_\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$), $\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$.

shift of concept: $\mathrm{𝚘𝚛𝚍𝚎𝚛𝚎𝚍}_\mathrm{𝚗𝚟𝚎𝚌𝚝𝚘𝚛}$ ($\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$ replaced by $\mathrm{𝚟𝚎𝚌𝚝𝚘𝚛}$ and $\le$ replaced by $\mathrm{𝚕𝚎𝚡}_\mathrm{𝚕𝚎𝚜𝚜𝚎𝚚}$).

Keywords
Arc input(s)

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

Arc generator
$\mathrm{𝐶𝐿𝐼𝑄𝑈𝐸}$$↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1},\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}\right)$

Arc arity
Arc constraint(s)
$\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1}.\mathrm{𝚟𝚊𝚛}=\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}.\mathrm{𝚟𝚊𝚛}$
Graph property(ies)
$\mathrm{𝐍𝐒𝐂𝐂}$$=\mathrm{𝙽𝚅𝙰𝙻}$

Graph class
$\mathrm{𝙴𝚀𝚄𝙸𝚅𝙰𝙻𝙴𝙽𝙲𝙴}$

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{𝐍𝐒𝐂𝐂}$ 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{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection. The 2 following values 6 and 8 are used by the variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection.

Automaton

A first systematic approach for creating an automaton that only recognises the solutions of the $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}_\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$ constraint could be to:

However this approach is not going to scale well in practice since the automaton associated with the $\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$ 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{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}_\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$ 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{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ contains at least one variable (i.e., $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|\ge 1$). Let $l$, $m$, $n$, $\mathrm{𝑚𝑖𝑛}$ and $\mathrm{𝑚𝑎𝑥}$ respectively denote the minimum and maximum possible value of variable $\mathrm{𝙽𝚅𝙰𝙻}$, the number of variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$, the smallest value that can be assigned to the variables of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$, and the largest value that can be assigned to the variables of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$. Let $s=\mathrm{𝑚𝑎𝑥}-\mathrm{𝑚𝑖𝑛}+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{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ 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{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}_\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$ 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\le i\le d,i\le j\le 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{𝙽𝚅𝙰𝙻}$ and correspond to those states ${s}_{ij}$ such that $i$ is a possible value for variable $\mathrm{𝙽𝚅𝙰𝙻}$. Note that we assume no further restriction on the domain of $\mathrm{𝙽𝚅𝙰𝙻}$ (otherwise the set of terminal states needs to be reduced in order to reflect the current set of possible values of $\mathrm{𝙽𝚅𝙰𝙻}$). Three classes of transitions are respectively defined in the following way:

1. There is a transition, labelled by $\mathrm{𝑚𝑖𝑛}+j-1$, from the initial state ${s}_{00}$ to the state ${s}_{1j}$ $\left(1\le j\le s\right)$.

2. There is a loop, labelled by $\mathrm{𝑚𝑖𝑛}+j-1$ for every state ${s}_{ij}$ $\left(1\le i\le d,i\le j\le s\right)$.

3. $\forall i\in \left[1,d-1\right],\forall j\in \left[i,s\right],\forall k\in \left[j+1,s\right]$ there is a transition labelled by $\mathrm{𝑚𝑖𝑛}+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{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}_\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$ constraint of the Example slot. For this purpose, we assume that variable $\mathrm{𝙽𝚅𝙰𝙻}$ is fixed to value 2 and that variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ 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{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}_\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ 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).