Global Constraint Catalog: Cbig

5.51. big_peak

DESCRIPTION

LINKS

AUTOMATON

Origin

Derived from $𝚙𝚎𝚊𝚔$ .

Constraint

$𝚋𝚒𝚐_𝚙𝚎𝚊𝚔 (𝙽, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂, 𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴)$

Arguments

$𝙽$	$𝚍𝚟𝚊𝚛$
$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$
$𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴$	$𝚒𝚗𝚝$

Restrictions

𝙽 \geq 0

2 * 𝙽 \leq 𝚖𝚊𝚡 (| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | - 1, 0)

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴 \geq 0

Purpose

A variable $V_{p}$ ( $1 < p < m$ ) of the sequence of variables $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 = V_{1}, \dots, V_{m}$ is a peak if and only if there exists an $i$ ( $1 < i \leq p$ ) such that $V_{i - 1} < V_{i}$ and $V_{i} = V_{i + 1} = \dots = V_{p}$ and $V_{p} > V_{p + 1}$ . Similarly a variable $V_{v}$ ( $1 < k < m$ ) is a valley if and only if there exists an $i$ $(1 < i \leq v)$ such that $V_{i - 1} > V_{i}$ and $V_{i} = V_{i + 1} = \dots = V_{v}$ and $V_{v} < V_{v + 1}$ . A peak variable $V_{p}$ ( $1 < p < m$ ) is a potential big peak wrt a non-negative integer $𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴$ if and only if:

$V_{p}$ is a peak,
$\exists i, j \in [1, m] | i < p < j$ , $V_{i}$ is a valley (or $i = 1$ if there is no valley before position $p$ ), $V_{j}$ is a valley (or $i = m$ if there is no valley after position $p$ ), $V_{p} - V_{i} > 𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴$ , and $V_{p} - V_{j} > 𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴$ .

Let $i_{p}$ and $j_{p}$ be the largest $i$ and the smallest $j$ satisfying condition 2. Now a potential big peak $V_{p}$ ( $1 < p < m$ ) is a big peak if and only if the interval $[i, j]$ does not contain any potential big peak that is strictly higher than $V_{p}$ . The constraint $𝚋𝚒𝚐_𝚙𝚎𝚊𝚔$ holds if and only if $𝙽$ is the total number of big peaks of the sequence of variables $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Example

(7, 〈4, 2, 2, 4, 3, 8, 6, 7, 7, 9, 5, 6, 3, 12, 12, 6, 6, 8, 4, 5, 1〉, 0)

(4, 〈4, 2, 2, 4, 3, 8, 6, 7, 7, 9, 5, 6, 3, 12, 12, 6, 6, 8, 4, 5, 1〉, 1)

As shown part Part (A) of Figure 5.51.1, the first $𝚋𝚒𝚐_𝚙𝚎𝚊𝚔$ constraint holds since the sequence $42243867795631212668451$ contains seven big peaks wrt a tolerance of 0 (i.e., we consider standard peaks).

As shown part Part (B) of Figure 5.51.1, the second $𝚋𝚒𝚐_𝚙𝚎𝚊𝚔$ constraint holds since the same sequence $42243867795631212668451$ contains only four big peaks wrt a tolerance of 1.

Figure 5.51.1. Illustration of the Example slot: Part (A) a sequence of 21 variables $V_{1}$ , $V_{2}$ , ..., $V_{21}$ respectively fixed to values 4, 2, 2, 4, 3, 8, 6, 7, 7, 9, 5, 6, 3, 12, 12, 6, 6, 8, 4, 5, 1 and its corresponding 7 peaks ( $𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴 = 0$ corresponds to standard peaks) with their respective heights $h_{1}^{0} = 1$ , $h_{2}^{0} = 2$ , $h_{3}^{0} = 3$ , $h_{4}^{0} = 1$ , $h_{5}^{0} = 6$ , $h_{6}^{0} = 2$ , $h_{7}^{0} = 1$ (the left and right hand sides of each peak are coloured in light orange and light red) Part (B) the same sequence of variables and its 4 big peaks when $𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴 = 1$ with their respective heights $h_{1}^{1} = 2$ , $h_{2}^{1} = 3$ , $h_{3}^{1} = 6$ , $h_{4}^{1} = 2$

Typical

𝙽 \geq 1

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

𝚛𝚊𝚗𝚐𝚎

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

𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴 > 1

Symmetries

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

Arg. properties

Functional dependency: $𝙽$ determined by $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ and $𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴$ .
Contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝙽 = 0$ and $𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴 = 0$ .

Usage

Useful for constraining the number of big peaks of a sequence of domain variables, by ignoring too small valleys that artificially create small peaks wrt $𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴$ .

See also

specialisation: $𝚙𝚎𝚊𝚔$ (the tolerance is set to 0 and removed).

Keywords

characteristic of a constraint: automaton, automaton with counters.

combinatorial object: sequence.

constraint arguments: pure functional dependency.

modelling: functional dependency.

Automaton: Figure 5.51.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.51.2. Automaton for the $𝚋𝚒𝚐_𝚙𝚎𝚊𝚔$ constraint where $C$ , $S$ , $P$ , $𝑚𝑖𝑛$ and $Δ$ respectively stand for the number of big peaks already encountered, the altitude at the start of the current potential big peak, the altitude of the current potential big peak, the smallest value that can be assigned to a variable of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ , the $𝚃𝙾𝙻𝙴𝚁𝙰𝙽𝙲𝙴$ parameter

Global Constraint Catalog

5. Global Constraint Catalogue

5.51. big_peak