## 5.417. valley

Origin
Constraint

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

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

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

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

The first $\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$ constraint holds since the sequence $11488271$ contains one valley that corresponds to the variable that is assigned to value 2.

##### Figure 5.417.1. Illustration of the first example of the Example slot: a sequence of eight variables ${V}_{1}$, ${V}_{2}$, ${V}_{3}$, ${V}_{4}$, ${V}_{5}$, ${V}_{6}$, ${V}_{7}$, ${V}_{8}$ respectively fixed to values 1, 1, 4, 8, 8, 2, 7, 1 and its corresponding unique valley ($𝙽=1$) All solutions

Figure 5.417.2 gives all solutions to the following non ground instance of the $\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$ constraint: $𝙽\in \left[1,2\right]$, ${V}_{1}\in \left[0,1\right]$, ${V}_{2}\in \left[0,2\right]$, ${V}_{3}\in \left[0,2\right]$, ${V}_{4}\in \left[0,1\right]$, $\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$$\left(𝙽,〈{V}_{1},{V}_{2},{V}_{3},{V}_{4}〉\right)$.

##### Figure 5.417.2. All solutions corresponding to the non ground example of the $\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$ constraint of the All solutions slot where each valley is coloured in orange Typical
 $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>2$ $\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}\right)>1$
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
• Functional dependency: $𝙽$ determined by $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

• Contractible wrt. $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ when $𝙽=0$.

Usage

Useful for constraining the number of valleys of a sequence of domain variables.

Remark

Since the arity of the arc constraint is not fixed, the $\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$ constraint cannot be currently described with the graph-based representation. However, this would not hold anymore if we were introducing a slot that specifies how to merge adjacent vertices of the final graph.

Counting
 Length ($n$) 2 3 4 5 6 7 8 Solutions 9 64 625 7776 117649 2097152 43046721

Number of solutions for $\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$: domains $0..n$  Length ($n$)2345678
Total9646257776117649209715243046721
 Parameter value

095029517921108869498439791
1-1433053137352894443011654622
2---67133033101092224895038
3-----723026057270

Solution count for $\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$: domains $0..n$  generalisation: $\mathrm{𝚋𝚒𝚐}_\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$ (a tolerance parameter is added for counting only big valleys).

specialisation: $\mathrm{𝚗𝚘}_\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$ (the variable counting the number of valleys is set to 0 and removed).

Keywords
Cond. implications

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

with  $𝙽>0$

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

when  $\mathrm{𝙽𝚅𝙰𝙻}=2$.

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

implies $\mathrm{𝚒𝚗𝚏𝚕𝚎𝚡𝚒𝚘𝚗}$$\left(𝙽,\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$

when  $𝙽=$$\mathrm{𝚙𝚎𝚊𝚔}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}\right)+\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}\right)$.

Automaton

Figure 5.417.3 depicts the automaton associated with the $\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.417.3. Automaton of the $\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$ constraint ##### Figure 5.417.4. Hypergraph of the reformulation corresponding to the automaton of the $\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$ constraint (since all states of the automaton are accepting there is no restriction on the last variable ${Q}_{n-1}$) ##### Figure 5.417.5. Glue matrix of the $\mathrm{𝚟𝚊𝚕𝚕𝚎𝚢}$ constraint
 $s$ $\left({\left\{<|=\right\}}^{*}\right)$ $u$ $\left(>{\left\{>|=\right\}}^{*}\right)$ $s$ $\left({\left\{<|=\right\}}^{*}\right)$ $\stackrel{\to }{C}+\stackrel{←}{C}$ $\stackrel{\to }{C}+\stackrel{←}{C}$ $u$ $\left(>{\left\{>|=\right\}}^{*}\right)$ $\stackrel{\to }{C}+\stackrel{←}{C}$ $\stackrel{\to }{C}+1+\stackrel{←}{C}$  ##### Figure 5.417.6. Illustrating the use of the state pair $\left(u,u\right)$ of the glue matrix for linking $𝙽$ with the counters variables obtained after reading the prefix $1,1,4,8,8,2$ and corresponding suffix $2,7,1$ of the sequence $1,1,4,8,8,2,7,1$; note that the suffix $2,7,1$ (in pink) is proceed in reverse order; the left (resp. right) table shows the initialisation (for $i=0$) and the evolution (for $i>0$) of the state of the automaton and its counter $C$ upon reading the prefix $1,1,4,8,8,2$ (resp. the reverse suffix $1,7,2$). 