Global Constraint Catalog: Cno

5.279. no_valley

DESCRIPTION

LINKS

AUTOMATON

Origin

Derived from $𝚟𝚊𝚕𝚕𝚎𝚢$ .

Constraint

$𝚗𝚘_𝚟𝚊𝚕𝚕𝚎𝚢 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

Argument

𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂

𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)

Restrictions

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

Purpose

A variable $V_{k}$ $(1 < k < m)$ of the sequence of variables $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 = V_{1}, \dots, V_{m}$ is a valley 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}$ . The total number of valleys of the sequence of variables $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ is equal to 0.

Example

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

The $𝚗𝚘_𝚟𝚊𝚕𝚕𝚎𝚢$ constraint holds since the sequence $114882$ does not contain any valley.

Figure 5.279.1. Illustration of the Example slot: a sequence of five variables $V_{1}$ , $V_{2}$ , $V_{3}$ , $V_{4}$ , $V_{5}$ , $V_{6}$ respectively fixed to values 1, 1, 4, 8, 8, 2 without any valley

Typical

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

𝚛𝚊𝚗𝚐𝚎

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

Symmetries

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

Arg. properties

Contractible wrt. $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Counting

Length ( $n$ )	2	3	4	5	6	7	8
Solutions	9	50	295	1792	11088	69498	439791

Number of solutions for $𝚗𝚘_𝚟𝚊𝚕𝚕𝚎𝚢$ : domains $0 . . n$

ctrs/no_valley-2-tikz

ctrs/no_valley-3-tikz

See also

comparison swapped: $𝚗𝚘_𝚙𝚎𝚊𝚔$ .

generalisation: $𝚟𝚊𝚕𝚕𝚎𝚢$ (introduce a $𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎$ counting the number of valleys).

implied by: $𝚍𝚎𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ , $𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚘𝚗𝚝𝚒𝚐𝚞𝚒𝚝𝚢$ , $𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ .

implies: $𝚊𝚕𝚕_𝚎𝚚𝚞𝚊𝚕_𝚟𝚊𝚕𝚕𝚎𝚢_𝚖𝚒𝚗$ .

related: $𝚙𝚎𝚊𝚔$ .

Keywords

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

combinatorial object: sequence.

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

Automaton: Figure 5.279.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.279.2. Automaton of the $𝚗𝚘_𝚟𝚊𝚕𝚕𝚎𝚢$ constraint

Figure 5.279.3. 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}$ )

Global Constraint Catalog

5. Global Constraint Catalogue

5.279. no_valley

Figure 5.279.1. Illustration of the Example slot: a sequence of five variables $V_{1}$ , $V_{2}$ , $V_{3}$ , $V_{4}$ , $V_{5}$ , $V_{6}$ respectively fixed to values 1, 1, 4, 8, 8, 2 without any valley

Figure 5.279.2. Automaton of the $𝚗𝚘_𝚟𝚊𝚕𝚕𝚎𝚢$ constraint

Figure 5.279.3. 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}$ )

Global Constraint Catalog

5. Global Constraint Catalogue

5.279. no_valley

Figure 5.279.1. Illustration of the Example slot: a sequence of five variables V 1 , V 2 , V 3 , V 4 , V 5 , V 6 respectively fixed to values 1, 1, 4, 8, 8, 2 without any valley

Figure 5.279.2. Automaton of the 𝚗𝚘_𝚟𝚊𝚕𝚕𝚎𝚢 constraint

Figure 5.279.3. 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.279.1. Illustration of the Example slot: a sequence of five variables $V_{1}$ , $V_{2}$ , $V_{3}$ , $V_{4}$ , $V_{5}$ , $V_{6}$ respectively fixed to values 1, 1, 4, 8, 8, 2 without any valley

Figure 5.279.2. Automaton of the $𝚗𝚘_𝚟𝚊𝚕𝚕𝚎𝚢$ constraint

Figure 5.279.3. 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}$ )