Global Constraint Catalog: Cpeak

5.318. 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}, \dots, V_{m}$ is a peak if and only if there exists an $i$ (with $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}$ . $𝙽$ is the total number of peaks of the sequence of variables $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Example

(2, 〈1, 1, 4, 8, 6, 2, 7, 1〉)

(0, 〈1, 1, 4, 4, 4, 6, 7, 7〉)

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

The first $𝚙𝚎𝚊𝚔$ 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.318.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, 6, 2, 7, 1 and its corresponding two peaks ( $𝙽 = 2$ )

All solutions

Figure 5.318.2 gives all solutions to the following non ground instance of the $𝚙𝚎𝚊𝚔$ constraint: $𝙽 \in [1, 2]$ , $V_{1} \in [1, 2]$ , $V_{2} = 2$ , $V_{3} \in [1, 2]$ , $V_{4} \in [1, 2]$ , $V_{5} \in [2, 3]$ , $𝚙𝚎𝚊𝚔$ $(𝙽, 〈 V_{1}, V_{2}, V_{3}, V_{4}, V_{5} 〉)$ .

Figure 5.318.2. All solutions corresponding to the non ground example of the $𝚙𝚎𝚊𝚔$ constraint of the All solutions slot where each peak is coloured in orange

Typical

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

𝚛𝚊𝚗𝚐𝚎

(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) > 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 $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .
Contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ when $𝙽 = 0$ .

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 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 $𝚙𝚎𝚊𝚔$ : domains $0 . . n$

ctrs/peak-3-tikz

ctrs/peak-4-tikz

Length (

n

)

Total

625

7776

117649

2097152

43046721

Parameter

value

295

1792

11088

69498

439791

330

5313

73528

944430

11654622

671

33033

1010922

24895038

72302

6057270

Solution count for $𝚙𝚎𝚊𝚔$ : domains $0 . . n$

ctrs/peak-5-tikz

ctrs/peak-6-tikz

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

generalisation: $𝚋𝚒𝚐_𝚙𝚎𝚊𝚔$ (a tolerance parameter is added for counting only big peaks).

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

Keywords

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

combinatorial object: sequence.

constraint arguments: reverse of a constraint, pure functional dependency.

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

filtering: glue matrix.

modelling: functional dependency.

Cond. implications

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

with $𝙽 > 0$

implies $𝚊𝚝𝚕𝚎𝚊𝚜𝚝_𝚗𝚟𝚊𝚕𝚞𝚎$ $(𝙽𝚅𝙰𝙻, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

when $𝙽𝚅𝙰𝙻 = 2$ .

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

implies $𝚒𝚗𝚏𝚕𝚎𝚡𝚒𝚘𝚗$ $(𝙽, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

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

Automaton

Figure 5.318.3 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.318.3. Automaton of the $𝚙𝚎𝚊𝚔$ constraint

Figure 5.318.4. Hypergraph of the reformulation corresponding to the automaton of the $𝚙𝚎𝚊𝚔$ constraint (since all states of the automaton are accepting there is no restriction on the last variable $Q_{n - 1}$ )

Figure 5.318.5. Glue matrix of the $𝚙𝚎𝚊𝚔$ constraint

	$s$ $({> \| =}^{*})$	$u$ $(< {< \| =}^{*})$
$s$ $({> \| =}^{*})$	$\vec{C} + \overset{\leftarrow}{C}$	$\vec{C} + \overset{\leftarrow}{C}$
$u$ $(< {< \| =}^{*})$	$\vec{C} + \overset{\leftarrow}{C}$	$\vec{C} + 1 + \overset{\leftarrow}{C}$

Figure 5.318.6. Illustrating the use of the state pair $(u, u)$ of the glue matrix for linking $𝙽$ with the counters variables obtained after reading the prefix $1, 1, 4, 8$ and corresponding suffix $8, 6, 2, 7, 1$ of the sequence $1, 1, 4, 8, 6, 2, 7, 1$ ; note that the suffix $8, 6, 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 of its counter $C$ upon reading the prefix $1, 1, 4, 8$ (resp. the suffix $1, 7, 2, 6, 8$ ).

Global Constraint Catalog

5. Global Constraint Catalogue

5.318. peak

Figure 5.318.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, 6, 2, 7, 1 and its corresponding two peaks (𝙽=2)

Figure 5.318.2. All solutions corresponding to the non ground example of the 𝚙𝚎𝚊𝚔 constraint of the All solutions slot where each peak is coloured in orange

Figure 5.318.3. Automaton of the 𝚙𝚎𝚊𝚔 constraint

Figure 5.318.4. Hypergraph of the reformulation corresponding to the automaton of the 𝚙𝚎𝚊𝚔 constraint (since all states of the automaton are accepting there is no restriction on the last variable Q n-1 )

Figure 5.318.5. Glue matrix of the 𝚙𝚎𝚊𝚔 constraint

Figure 5.318.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, 6, 2, 7, 1 and its corresponding two peaks ( $𝙽 = 2$ )

Figure 5.318.2. All solutions corresponding to the non ground example of the $𝚙𝚎𝚊𝚔$ constraint of the All solutions slot where each peak is coloured in orange

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

Figure 5.318.4. Hypergraph of the reformulation corresponding to the automaton of the $𝚙𝚎𝚊𝚔$ constraint (since all states of the automaton are accepting there is no restriction on the last variable $Q_{n - 1}$ )

Figure 5.318.5. Glue matrix of the $𝚙𝚎𝚊𝚔$ constraint