Global Constraint Catalog: Call_equal

5.6. all_equal_peak

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 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} = \dots = V_{k}$ and $V_{k} > V_{k + 1}$ .

Enforce all the peaks of the sequence $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ to be assigned the same value, i.e. to be located at the same altitude.

Example

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

The $𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕_𝚙𝚎𝚊𝚔$ constraint holds since the two peaks, in bold, of the sequence $15543527$ are located at the same altitude 5. Figure 5.6.1 depicts the solution associated with the example.

Figure 5.6.1. Illustration 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, 5, 5, 4, 3, 5, 2, 7 and its corresponding two peaks, in red, both located at altitude 5

Note that the $𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕_𝚙𝚎𝚊𝚔$ constraint does not enforce that the maximum value of the sequence $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ corresponds to the altitude of its peaks since, as shown by the example, the sequence can ends up with an increasing subsequence that go beyond the altitude of its peaks. It also does not enforce that the sequence $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ contains at least one peak.

All solutions

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

Figure 5.6.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

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

𝚛𝚊𝚗𝚐𝚎

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

𝚙𝚎𝚊𝚔

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

Symmetries

Items of $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ can be reversed.
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	9
Solutions	9	64	625	7330	93947	1267790	17908059	266201992

Number of solutions for $𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕_𝚙𝚎𝚊𝚔$ : domains $0 . . n$

ctrs/all_equal_peak-3-tikz

ctrs/all_equal_peak-4-tikz

See also

implied by: $𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕_𝚙𝚎𝚊𝚔_𝚖𝚊𝚡$ .

implies: $𝚍𝚎𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚙𝚎𝚊𝚔$ , $𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚙𝚎𝚊𝚔$ .

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 $𝚙𝚎𝚊𝚔$ $(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) > 1$

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

$•$ $𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕_𝚙𝚎𝚊𝚔 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

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

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

Automaton: Figure 5.6.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.6.3. Automaton for the $𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕_𝚙𝚎𝚊𝚔$ constraint (note the conditional transition from state $k$ to state $j$ testing that the counter $𝐴𝑙𝑡𝑖𝑡𝑢𝑑𝑒$ is equal to ${𝚅𝙰𝚁}_{i}$ for enforcing that all peaks are located at the same altitude)

Figure 5.6.4. 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.6. all_equal_peak

Figure 5.6.1. Illustration 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, 5, 5, 4, 3, 5, 2, 7 and its corresponding two peaks, in red, both located at altitude 5

Figure 5.6.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.6.3. Automaton for the 𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕_𝚙𝚎𝚊𝚔 constraint (note the conditional transition from state k to state j testing that the counter 𝐴𝑙𝑡𝑖𝑡𝑢𝑑𝑒 is equal to 𝚅𝙰𝚁 i for enforcing that all peaks are located at the same altitude)

Figure 5.6.1. Illustration 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, 5, 5, 4, 3, 5, 2, 7 and its corresponding two peaks, in red, both located at altitude 5

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