Global Constraint Catalog: Cpeak

5.267. peak

DESCRIPTION

LINKS

AUTOMATON

Origin

Derived from $𝚒𝚗𝚏𝚕𝚎𝚡𝚒𝚘𝚗$ .

Constraint

$𝚙𝚎𝚊𝚔 (𝙽, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

Arguments

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

Restrictions

𝙽 \geq 0

2 * 𝙽 \leq 𝚖𝚊𝚡 (| 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | - 1, 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 total number of peaks of the sequence of variables $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Example

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

The $𝚙𝚎𝚊𝚔$ constraint holds since the sequence $11486271$ contains two peaks that respectively correspond to the variables that are assigned to values 8 and 7.

Figure 5.267.1. The sequence and its two peaks

Symmetries

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

Usage

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

Remark

Since the arity of the arc constraint is not fixed, the $𝚙𝚎𝚊𝚔$ constraint cannot be currently described. However, this would not hold anymore if we were introducing a slot that specifies how to merge adjacent vertices of the final graph.

comparison swapped: $𝚟𝚊𝚕𝚕𝚎𝚢$ .

related: $𝚗𝚘_𝚟𝚊𝚕𝚕𝚎𝚢$ .

specialisation: $𝚗𝚘_𝚙𝚎𝚊𝚔$ (the variable counting the number of peaks is set to 0 and removed).

Keywords

characteristic of a constraint: automaton, automaton with counters.

combinatorial object: sequence.

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

Automaton: Figure 5.267.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.267.2. Automaton of the $𝚙𝚎𝚊𝚔$ constraint

Figure 5.267.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚙𝚎𝚊𝚔$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.267. peak

Figure 5.267.1. The sequence and its two peaks

Figure 5.267.2. Automaton of the $𝚙𝚎𝚊𝚔$ constraint

Figure 5.267.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.267. peak

Figure 5.267.1. The sequence and its two peaks

Figure 5.267.2. Automaton of the 𝚙𝚎𝚊𝚔 constraint

Figure 5.267.3. Hypergraph of the reformulation corresponding to the automaton of the 𝚙𝚎𝚊𝚔 constraint

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

Figure 5.267.2. Automaton of the $𝚙𝚎𝚊𝚔$ constraint

Figure 5.267.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚙𝚎𝚊𝚔$ constraint