Global Constraint Catalog: Cincreasing

5.191. increasing_valley

DESCRIPTION

LINKS

AUTOMATON

Origin

Derived from $𝚟𝚊𝚕𝚕𝚎𝚢$ and $𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ .

Constraint

$𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚟𝚊𝚕𝚕𝚎𝚢 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

Argument

𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂

𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)

Restrictions

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | > 0

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚟𝚊𝚛)

Purpose

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

When considering all the valleys of the sequence $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ from left to right enforce all valleys to be increasing, i.e. the altitude of each valley is greater than or equal to the altitude of its preceding valley when it exists.

Example

(〈3, 5, 1, 4, 3, 5, 3, 3, 7, 2〉)

The $𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚟𝚊𝚕𝚕𝚎𝚢$ constraint holds since the sequence $3514353372$ contains three valleys, in bold, that are increasing.

Figure 5.191.1. Illustration of the Example slot: a sequence of ten variables $V_{1}$ , $V_{2}$ , $V_{3}$ , $V_{4}$ , $V_{5}$ , $V_{6}$ , $V_{7}$ , $V_{8}$ , $V_{9}$ , $V_{10}$ respectively fixed to values 3, 5, 1, 4, 3, 5, 3, 3, 7, 2 and its corresponding three valleys, in red, respectively located at altitudes 1, 3 and 3

Typical

| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | \geq 7

𝚛𝚊𝚗𝚐𝚎

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) > 1

𝚟𝚊𝚕𝚕𝚎𝚢

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) \geq 3

Symmetry

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

Arg. properties

Prefix-contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .
Suffix-contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Counting

Length ( $n$ )	2	3	4	5	6	7	8
Solutions	9	64	625	7553	105798	1666878	29090469

Number of solutions for $𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚟𝚊𝚕𝚕𝚎𝚢$ : domains $0 . . n$

ctrs/increasing_valley-2-tikz

ctrs/increasing_valley-3-tikz

See also

implied by: $𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕_𝚟𝚊𝚕𝚕𝚎𝚢$ .

Keywords

characteristic of a constraint: automaton, automaton with counters, automaton with same input symbol.

combinatorial object: sequence.

constraint network structure: sliding cyclic(1) constraint network(2).

Cond. implications

$𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚟𝚊𝚕𝚕𝚎𝚢 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

with $𝚟𝚊𝚕𝚕𝚎𝚢$ $(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) > 0$

implies $𝚗𝚘𝚝_𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕$ $(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$ .

Automaton: Figure 5.191.2 depicts the automaton associated with the $𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚟𝚊𝚕𝚕𝚎𝚢$ constraint. To each pair of consecutive variables $({𝚅𝙰𝚁}_{i}, {𝚅𝙰𝚁}_{i + 1})$ of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ corresponds a signature variable $S_{i}$ . The following signature constraint links ${𝚅𝙰𝚁}_{i}$ , ${𝚅𝙰𝚁}_{i + 1}$ and $S_{i}$ : $({𝚅𝙰𝚁}_{i} < {𝚅𝙰𝚁}_{i + 1} \Leftrightarrow S_{i} = 0) \land ({𝚅𝙰𝚁}_{i} = {𝚅𝙰𝚁}_{i + 1} \Leftrightarrow S_{i} = 1) \land ({𝚅𝙰𝚁}_{i} > {𝚅𝙰𝚁}_{i + 1} \Leftrightarrow S_{i} = 2)$ .

Figure 5.191.2. Automaton for the $𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚟𝚊𝚕𝚕𝚎𝚢$ constraint (note the conditional transition from state $w$ to state $v$ testing that the counter $𝐴𝑙𝑡𝑖𝑡𝑢𝑑𝑒$ is less than or equal to ${𝚅𝙰𝚁}_{i}$ for enforcing that all valleys from left to right are in increasing altitude)

Figure 5.191.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚟𝚊𝚕𝚕𝚎𝚢$ constraint where $A_{i}$ stands for the value of the counter $𝐴𝑙𝑡𝑖𝑡𝑢𝑑𝑒$ (since all states of the automaton are accepting there is no restriction on the last variable $Q_{n - 1}$ )

Global Constraint Catalog

5. Global Constraint Catalogue

5.191. increasing_valley

Figure 5.191.1. Illustration of the Example slot: a sequence of ten variables V 1 , V 2 , V 3 , V 4 , V 5 , V 6 , V 7 , V 8 , V 9 , V 10 respectively fixed to values 3, 5, 1, 4, 3, 5, 3, 3, 7, 2 and its corresponding three valleys, in red, respectively located at altitudes 1, 3 and 3