Conjoin $\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$ and $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}$.

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

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

• The values of the collection $\langle 6,6,8,8,8\rangle$ are sorted in increasing order.

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

Figure 5.161.1. The solution associated with the example

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

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

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 [1,2]$, $V_2\in [1,2]$, $V_1\le V_2$, $\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$($2,\langle V_1,V_2\rangle$), this hinders propagation (i.e., the unique solution $V_1=1$, $V_2=2$ is not directly obtained after stating all the previous constraints).

increasingNValue in Choco.

implies: $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}$ (remove $\mathrm{𝙽𝚅𝙰𝙻}$ parameter from $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}\_\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$), $\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$.

related: $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}\_\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}\_\mathrm{𝚌𝚑𝚊𝚒𝚗}$.

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

constraint type: counting constraint, value partitioning constraint, order constraint.

final graph structure: strongly connected component, equivalence.

modelling: number of distinct equivalence classes, number of distinct values.

symmetry: symmetry.

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

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.

Figure 5.161.2. Initial and final graph of the $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}\_\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$ constraint

(a)	(b)

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

• First, create an automaton that recognises the solutions of the $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}$ constraint.

• Second, create an automaton that recognises the solutions of the $\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$ constraint.

• Third, make the product of the two previous automata and minimise the resulting automaton.

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., $\left|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right|\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(m,n,s)$. The $\frac{s·(s+1)}{2}-\frac{(s-d)·(s-d+1)}{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·(s+1)}{2}-\frac{(s-d)·(s-d+1)}{2}$ states labelled by $s_{ij}$ $(1\le i\le d,i\le j\le s)$. 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}$ $(1\le j\le s)$.

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

3. $\forall i\in [1,d-1],\forall j\in [i,s],\forall k\in [j+1,s]$ 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·(s+1)}{2}-\frac{(s-d)·(s-d+1)}{2}$ transitions of class 2, and $\frac{(s-1)·s·(s+1)}{6}-\frac{(s-d)·(s-d+1)·(s-d+2)}{6}$ transitions of class 3.

Note that all states $s_{ij}$ such that $i+s-j<l$ 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 $[6,8]$. 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).

Figure 5.161.3. Automaton – Part A – and simplified automaton – Part B – of the $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}\_\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$ constraint of the Example slot: the path corresponding to the solution $\langle 6,6,8,8,8\rangle$ is depicted by thick arcs