5.97. deepest_valley

DESCRIPTIONLINKSAUTOMATON
Origin

Derived from πšŸπšŠπš•πš•πšŽπš’.

Constraint

πšπšŽπšŽπš™πšŽπšœπš_πšŸπšŠπš•πš•πšŽπš’(π™³π™΄π™Ώπšƒπ™·,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Arguments
π™³π™΄π™Ώπšƒπ™·πšπšŸπšŠπš›
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
π™³π™΄π™Ώπšƒπ™·β‰₯0
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›β‰₯0
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
Purpose

A variable V k (1<k<m) of the sequence of variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚=V 1 ,...,V m is a valley if and only if there exists an i (1<i≀k) such that V i-1 >V i and V i =V i+1 =...=V k and V k <V k+1 . π™³π™΄π™Ώπšƒπ™· is the minimum value of the valley variables. If no such variable exists π™³π™΄π™Ώπšƒπ™· is equal to the default value π™Όπ™°πš‡π™Έπ™½πšƒ.

Example
2,πšŸπšŠπš›-5,πšŸπšŠπš›-3,πšŸπšŠπš›-4,πšŸπšŠπš›-8,πšŸπšŠπš›-8,πšŸπšŠπš›-2,πšŸπšŠπš›-7,πšŸπšŠπš›-1

The πšπšŽπšŽπš™πšŽπšœπš_πšŸπšŠπš•πš•πšŽπš’ constraint holds since 2 is the deepest valley of the sequence 5 3 4 8 8 2 7 1.

Figure 5.97.1. The sequence and its deepest valley
ctrs/deepest_valley1
Typical
π™³π™΄π™Ώπšƒπ™·β‰€πš–πšŠπš‘πšŸπšŠπš•(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›)
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
πš›πšŠπš—πšπšŽ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›)>1
Symmetry

Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ can be reversed.

See also

common keyword: πš‘πš’πšπš‘πšŽπšœπš_πš™πšŽπšŠπš”, πšŸπšŠπš•πš•πšŽπš’Β (sequence).

Keywords

characteristic of a constraint: maxint, automaton, automaton with counters.

combinatorial object: sequence.

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

Automaton

FigureΒ 5.97.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 β‡”πš‚ i =0 ∧ πš…π™°πš i =πš…π™°πš i+1 β‡”πš‚ i =1 ∧ πš…π™°πš i >πš…π™°πš i+1 β‡”πš‚ i =2.

Figure 5.97.2. Automaton of the πšπšŽπšŽπš™πšŽπšœπš_πšŸπšŠπš•πš•πšŽπš’ constraint
ctrs/deepest_valley2
Figure 5.97.3. Hypergraph of the reformulation corresponding to the automaton of the πšπšŽπšŽπš™πšŽπšœπš_πšŸπšŠπš•πš•πšŽπš’ constraint
ctrs/deepest_valley3