Global Constraint Catalog: Cmin_increasing

5.254. min_increasing_slope

DESCRIPTION

LINKS

AUTOMATON

Origin

Motivated by time series.

Constraint

$𝚖𝚒𝚗_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚕𝚘𝚙𝚎 (𝙼𝙸𝙽, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

Arguments

$𝙼𝙸𝙽$	$𝚍𝚟𝚊𝚛$
$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$	$𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛 - 𝚍𝚟𝚊𝚛)$

Restrictions

𝙼𝙸𝙽 \geq 0

𝙼𝙸𝙽 <

𝚛𝚊𝚗𝚐𝚎

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

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

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

Purpose

Given a sequence of variables $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 = V_{1}, V_{2}, \dots, V_{n}$ , sets $𝙼𝙸𝙽$ to 0 if $∄ i \in [1, n - 1] | V_{i} < V_{i + 1}$ , otherwise sets $𝙼𝙸𝙽$ to ${min}_{i \in [1, n - 1] | V_{i} < V_{i + 1}} (V_{i + 1} - V_{i})$ .

Example

(3, 〈1, 1, 5, 8, 6, 2, 2, 1, 5〉)

(0, 〈8, 8, 2, 0, 0〉)

(9, 〈1, 1, 0, 9, 6〉)

The first $𝚖𝚒𝚗_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚕𝚘𝚙𝚎$ constraint holds since the sequence $115862215$ contains two increasing subsequences $158$ and $15$ and the minimum slope is equal to $min (5 - 1, 8 - 5, 5 - 1) = 3$ as shown on Figure 5.254.1.

Figure 5.254.1. Illustration of the first example of the Example slot: a sequence of nine variables $V_{1}$ , $V_{2}$ , $V_{3}$ , $V_{4}$ , $V_{5}$ , $V_{6}$ , $V_{7}$ , $V_{8}$ , $V_{9}$ respectively fixed to values 1, 1, 5, 8, 6, 2, 2, 1, 5 and the corresponding minimum slope on the strictly increasing subsequences $158$ and $15$ ( $𝙼𝙸𝙽 = 3$ )

Typical

𝙼𝙸𝙽 > 1

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

𝚛𝚊𝚗𝚐𝚎

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

Symmetry

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

Arg. properties

Functional dependency: $𝙼𝙸𝙽$ determined by $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ .

Usage

Getting the minimum slope over the increasing sequences of time series.

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/min_increasing_slope-2-tikz

ctrs/min_increasing_slope-3-tikz

Length (

n

)

Total

625

7776

117649

2097152

43046721

Parameter

value

252

924

3432

12870

256

3512

56537

1051936

22280084

145

1864

28728

515372

10601773

1062

14729

255076

5106480

704

8853

133672

2475484

382

5266

78198

1369232

2612

41330

730161

18136

341618

129019

Solution count for $𝚖𝚒𝚗_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚕𝚘𝚙𝚎$ : domains $0 . . n$

ctrs/min_increasing_slope-4-tikz

ctrs/min_increasing_slope-5-tikz

Keywords

characteristic of a constraint: automaton, automaton with counters.

combinatorial object: sequence.

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

filtering: glue matrix.

modelling: functional dependency.

Cond. implications

$𝚖𝚒𝚗_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚕𝚘𝚙𝚎 (𝙼𝙸𝙽, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

with $𝚛𝚊𝚗𝚐𝚎$ $(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) = 𝙼𝙸𝙽 + 1$

implies $𝚖𝚊𝚡_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚕𝚘𝚙𝚎$ $(𝙼𝙰𝚇, 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

when $𝚛𝚊𝚗𝚐𝚎$ $(𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 . 𝚟𝚊𝚛) = 𝙼𝙰𝚇 + 1$ .

Automaton: Figure 5.254.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} \geq {𝚅𝙰𝚁}_{i + 1} \Leftrightarrow S_{i} = 0) \land ({𝚅𝙰𝚁}_{i} < {𝚅𝙰𝚁}_{i + 1} \Leftrightarrow S_{i} = 1)$ .

Figure 5.254.2. Automaton for the $𝚖𝚒𝚗_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚕𝚘𝚙𝚎$ constraint and its glue matrix (note that the reverse of $𝚖𝚒𝚗_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚕𝚘𝚙𝚎$ is $𝚖𝚒𝚗_𝚍𝚎𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐_𝚜𝚕𝚘𝚙𝚎$ )

Global Constraint Catalog

5. Global Constraint Catalogue

5.254. min_increasing_slope