Global Constraint Catalog: Chighest

5.150. highest_peak

DESCRIPTION

LINKS

AUTOMATON

Origin

Derived from $𝚙𝚎𝚊𝚔$ .

Constraint

$𝚑𝚒𝚐𝚑𝚎𝚜𝚝_𝚙𝚎𝚊𝚔 (𝙷𝙴𝙸𝙶𝙷𝚃, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

Arguments

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

Restrictions

𝙷𝙴𝙸𝙶𝙷𝚃 \geq 0

𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛 \geq 0

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

Purpose

A variable $V_{k}$ $(1 < k < m)$ of the sequence of variables $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 = V_{1}, ..., V_{m}$ is a peak 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} = ... = V_{k}$ and $V_{k} > V_{k + 1}$ . $𝙷𝙴𝙸𝙶𝙷𝚃$ is the maximum value of the peak variables. If no such variable exists $𝙷𝙴𝙸𝙶𝙷𝚃$ is equal to 0.

Example

(\begin{matrix} 8, 〈\begin{matrix} 𝚟𝚊𝚛 - 1, \\ 𝚟𝚊𝚛 - 1, \\ 𝚟𝚊𝚛 - 4, \\ 𝚟𝚊𝚛 - 8, \\ 𝚟𝚊𝚛 - 6, \\ 𝚟𝚊𝚛 - 2, \\ 𝚟𝚊𝚛 - 7, \\ 𝚟𝚊𝚛 - 1 \end{matrix}〉 \end{matrix})

The $𝚑𝚒𝚐𝚑𝚎𝚜𝚝_𝚙𝚎𝚊𝚔$ constraint holds since 8 is the maximum peak of the sequence $11486271$ .

Figure 5.150.1. The sequence and its highest peak

Typical

𝙷𝙴𝙸𝙶𝙷𝚃 > 0

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

𝚛𝚊𝚗𝚐𝚎

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

Symmetry

Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ can be reversed.

Keywords

characteristic of a constraint: automaton, automaton with counters.

combinatorial object: sequence.

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

Automaton

Figure 5.150.2 depicts the automaton associated with the $𝚑𝚒𝚐𝚑𝚎𝚜𝚝_𝚙𝚎𝚊𝚔$ constraint. To each pair of consecutive variables $({𝚅𝙰𝚁}_{i}, {𝚅𝙰𝚁}_{i + 1})$ of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ corresponds a signature variable $𝚂_{i}$ . The following signature constraint links ${𝚅𝙰𝚁}_{i}$ , ${𝚅𝙰𝚁}_{i + 1}$ and $𝚂_{i}$ :

${𝚅𝙰𝚁}_{i} > {𝚅𝙰𝚁}_{i + 1} \Leftrightarrow 𝚂_{i} = 0 \land {𝚅𝙰𝚁}_{i} = {𝚅𝙰𝚁}_{i + 1} \Leftrightarrow 𝚂_{i} = 1 \land {𝚅𝙰𝚁}_{i} < {𝚅𝙰𝚁}_{i + 1} \Leftrightarrow 𝚂_{i} = 2$ .

Figure 5.150.2. Automaton of the $𝚑𝚒𝚐𝚑𝚎𝚜𝚝_𝚙𝚎𝚊𝚔$ constraint

Figure 5.150.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚑𝚒𝚐𝚑𝚎𝚜𝚝_𝚙𝚎𝚊𝚔$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.150. highest_peak

Figure 5.150.1. The sequence and its highest peak

Figure 5.150.2. Automaton of the $𝚑𝚒𝚐𝚑𝚎𝚜𝚝_𝚙𝚎𝚊𝚔$ constraint

Figure 5.150.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚑𝚒𝚐𝚑𝚎𝚜𝚝_𝚙𝚎𝚊𝚔$ constraint

W3C: XHTML - last update: 2010-12-6. SD.

Global Constraint Catalog

5. Global Constraint Catalogue

5.150. highest_peak

Figure 5.150.1. The sequence and its highest peak

Figure 5.150.2. Automaton of the 𝚑𝚒𝚐𝚑𝚎𝚜𝚝_𝚙𝚎𝚊𝚔 constraint

Figure 5.150.3. Hypergraph of the reformulation corresponding to the automaton of the 𝚑𝚒𝚐𝚑𝚎𝚜𝚝_𝚙𝚎𝚊𝚔 constraint

W3C: XHTML - last update: 2010-12-6. SD.

Figure 5.150.2. Automaton of the $𝚑𝚒𝚐𝚑𝚎𝚜𝚝_𝚙𝚎𝚊𝚔$ constraint

Figure 5.150.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚑𝚒𝚐𝚑𝚎𝚜𝚝_𝚙𝚎𝚊𝚔$ constraint