## 5.8. all_equal_valley

Origin
Constraint

$\mathrm{𝚊𝚕𝚕}_\mathrm{𝚎𝚚𝚞𝚊𝚕}_\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$

Argument
 $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$
Restrictions
 $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>0$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚟𝚊𝚛}\right)$
Purpose

A variable ${V}_{k}$ $\left(1 of the sequence of variables $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}={V}_{1},\cdots ,{V}_{m}$ is a valley if and only if there exists an $i$ $\left(1 such that ${V}_{i-1}>{V}_{i}$ and ${V}_{i}={V}_{i+1}=\cdots ={V}_{k}$ and ${V}_{k}<{V}_{k+1}$.

Enforce all the valleys of the sequence $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ to be assigned the same value, i.e. to be located at the same altitude.

Example
$\left(〈1,5,5,4,2,2,6,2,7〉\right)$

The $\mathrm{𝚊𝚕𝚕}_\mathrm{𝚎𝚚𝚞𝚊𝚕}_\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$ constraint holds since the two valleys, in bold, of the sequence $155422627$ are located at the same altitude 2. Figure 5.8.1 depicts the solution associated with the example.

##### Figure 5.8.1. Illustration of the Example slot: a sequence of nine variables ${V}_{1}$, ${V}_{2}$, ${V}_{3}$, ${V}_{4}$, ${V}_{5}$, ${V}_{6}$, ${V}_{7}$, ${V}_{8}$, ${V}_{9}$ respectively fixed to values 1, 5, 5, 4, 2, 2, 6, 2, 7 and its corresponding two valleys, in red, both located at altitude 2 Note that the $\mathrm{𝚊𝚕𝚕}_\mathrm{𝚎𝚚𝚞𝚊𝚕}_\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$ constraint does not enforce that the minimum value of the sequence $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ corresponds to the altitude of its valleys since, as shown by the example, the sequence can starts with an increasing subsequence that start below the altitude of its valleys. It also does not enforce that the sequence $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ contains at least one valley.

Typical
 $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|\ge 5$ $\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}\right)>1$ $\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}\right)\ge 2$
Symmetries
• Items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ can be reversed.

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

Arg. properties
• Prefix-contractible wrt. $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

• Suffix-contractible wrt. $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

Counting
 Length ($n$) 2 3 4 5 6 7 8 Solutions 9 64 625 7330 93947 1267790 17908059

Number of solutions for $\mathrm{𝚊𝚕𝚕}_\mathrm{𝚎𝚚𝚞𝚊𝚕}_\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$: domains $0..n$  Keywords
Cond. implications

$•$ $\mathrm{𝚊𝚕𝚕}_\mathrm{𝚎𝚚𝚞𝚊𝚕}_\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$

with  $\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}\right)>1$

implies $\mathrm{𝚜𝚘𝚖𝚎}_\mathrm{𝚎𝚚𝚞𝚊𝚕}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$.

$•$ $\mathrm{𝚊𝚕𝚕}_\mathrm{𝚎𝚚𝚞𝚊𝚕}_\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$

with  $\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}\right)>0$

implies $\mathrm{𝚗𝚘𝚝}_\mathrm{𝚊𝚕𝚕}_\mathrm{𝚎𝚚𝚞𝚊𝚕}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$.

Automaton

Figure 5.8.2 depicts the automaton associated with the $\mathrm{𝚊𝚕𝚕}_\mathrm{𝚎𝚚𝚞𝚊𝚕}_\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$ constraint. To each pair of consecutive variables $\left({\mathrm{𝚅𝙰𝚁}}_{i},{\mathrm{𝚅𝙰𝚁}}_{i+1}\right)$ of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ corresponds a signature variable ${S}_{i}$. The following signature constraint links ${\mathrm{𝚅𝙰𝚁}}_{i}$, ${\mathrm{𝚅𝙰𝚁}}_{i+1}$ and ${S}_{i}$: $\left({\mathrm{𝚅𝙰𝚁}}_{i}<{\mathrm{𝚅𝙰𝚁}}_{i+1}⇔{S}_{i}=0\right)\wedge \left({\mathrm{𝚅𝙰𝚁}}_{i}={\mathrm{𝚅𝙰𝚁}}_{i+1}⇔{S}_{i}=1\right)\wedge \left({\mathrm{𝚅𝙰𝚁}}_{i}>{\mathrm{𝚅𝙰𝚁}}_{i+1}⇔{S}_{i}=2\right)$.

##### Figure 5.8.2. Automaton for the $\mathrm{𝚊𝚕𝚕}_\mathrm{𝚎𝚚𝚞𝚊𝚕}_\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$ constraint (note the conditional transition from state $k$ to state $j$ testing that the counter $\mathrm{𝐴𝑙𝑡𝑖𝑡𝑢𝑑𝑒}$ is equal to ${\mathrm{𝚅𝙰𝚁}}_{i}$ for enforcing that all valleys are located at the same altitude) ##### Figure 5.8.3. Hypergraph of the reformulation corresponding to the automaton of the $\mathrm{𝚊𝚕𝚕}_\mathrm{𝚎𝚚𝚞𝚊𝚕}_\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$ constraint where ${A}_{i}$ stands for the value of the counter $\mathrm{𝐴𝑙𝑡𝑖𝑡𝑢𝑑𝑒}$ (since all states of the automaton are accepting there is no restriction on the last variable ${Q}_{n-1}$) 