5.350. valley

DESCRIPTIONLINKSAUTOMATON
Origin

Derived from πš’πš—πšπš•πšŽπš‘πš’πš˜πš—.

Constraint

πšŸπšŠπš•πš•πšŽπš’(𝙽,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Arguments
π™½πšπšŸπšŠπš›
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
𝙽β‰₯0
2*π™½β‰€πš–πšŠπš‘(|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-1,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 total number of valleys of the sequence of variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

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

The πšŸπšŠπš•πš•πšŽπš’ constraint holds since the sequence 1 1 4 8 8 2 7 1 contains one valley that corresponds to the variable that is assigned to value 2.

Figure 5.350.1. The sequence and its unique valley
ctrs/valley1
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 valleys 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.

See also

common keyword: πšπšŽπšŽπš™πšŽπšœπš_πšŸπšŠπš•πš•πšŽπš’, πš’πš—πšπš•πšŽπš‘πš’πš˜πš—Β (sequence).

comparison swapped: πš™πšŽπšŠπš”.

related: πš—πš˜_πš™πšŽπšŠπš”.

specialisation: πš—πš˜_πšŸπšŠπš•πš•πšŽπš’Β (the variable counting the number of valleys 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.350.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.350.2. Automaton of the πšŸπšŠπš•πš•πšŽπš’ constraint
ctrs/valley2
Figure 5.350.3. Hypergraph of the reformulation corresponding to the automaton of the πšŸπšŠπš•πš•πšŽπš’ constraint
ctrs/valley3