Global Constraint Catalog: Cstrictly

5.380. strictly_increasing

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

KOALOG

Constraint

$𝚜𝚝𝚛𝚒𝚌𝚝𝚕𝚢_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

Argument

𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂

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

Restriction

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

Purpose

The variables of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ are strictly increasing.

Example

(〈1, 3, 6, 8〉)

The $𝚜𝚝𝚛𝚒𝚌𝚝𝚕𝚢_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ constraint holds since $1 < 3 < 6 < 8$ .

Typical

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

Symmetry

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	9	10
Solutions	3	4	5	6	7	8	9	10	11

Number of solutions for $𝚜𝚝𝚛𝚒𝚌𝚝𝚕𝚢_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ : domains $0 . . n$

ctrs/strictly_increasing-1-tikz

ctrs/strictly_increasing-2-tikz

Systems

increasingNValue in Choco, rel in Gecode.

Used in

$𝚐𝚘𝚕𝚘𝚖𝚋$ , $𝚒𝚗𝚝_𝚟𝚊𝚕𝚞𝚎_𝚙𝚛𝚎𝚌𝚎𝚍𝚎_𝚌𝚑𝚊𝚒𝚗$ , $𝚖𝚊𝚡_𝚘𝚌𝚌_𝚘𝚏_𝚝𝚞𝚙𝚕𝚎𝚜_𝚘𝚏_𝚟𝚊𝚕𝚞𝚎𝚜$ .

comparison swapped: $𝚜𝚝𝚛𝚒𝚌𝚝𝚕𝚢_𝚍𝚎𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ .

implied by: $𝚐𝚘𝚕𝚘𝚖𝚋$ .

implies: $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ , $𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ .

uses in its reformulation: $𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝$ .

Keywords

characteristic of a constraint: automaton, automaton without counters, reified automaton constraint.

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

constraint type: decomposition, order constraint.

filtering: arc-consistency.

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$

Arc generator

𝑃𝐴𝑇𝐻

\mapsto 𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗 (𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1, 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2)

Arc arity

Arc constraint(s)

𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1 . 𝚟𝚊𝚛 < 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2 . 𝚟𝚊𝚛

Graph property(ies)

𝐍𝐀𝐑𝐂

= | 𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂 | - 1

Graph model

Parts (A) and (B) of Figure 5.380.1 respectively show the initial and final graph associated with the Example slot. Since we use the $𝐍𝐀𝐑𝐂$ graph property, the arcs of the final graph are stressed in bold.

Figure 5.380.1. Initial and final graph of the $𝚜𝚝𝚛𝚒𝚌𝚝𝚕𝚢_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ constraint


(a)	(b)

Automaton: Figure 5.380.2 depicts the automaton associated with the $𝚜𝚝𝚛𝚒𝚌𝚝𝚕𝚢_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ constraint. To each pair of consecutive variables $({𝚅𝙰𝚁}_{i}, {𝚅𝙰𝚁}_{i + 1})$ of the collection $𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$ corresponds a 0-1 signature variable $S_{i}$ . The following signature constraint links ${𝚅𝙰𝚁}_{i}$ , ${𝚅𝙰𝚁}_{i + 1}$ and $S_{i}$ : ${𝚅𝙰𝚁}_{i} \geq {𝚅𝙰𝚁}_{i + 1} \Leftrightarrow S_{i}$ .

Figure 5.380.2. Automaton of the $𝚜𝚝𝚛𝚒𝚌𝚝𝚕𝚢_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ constraint

Figure 5.380.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚜𝚝𝚛𝚒𝚌𝚝𝚕𝚢_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.380. strictly_increasing

Figure 5.380.1. Initial and final graph of the $𝚜𝚝𝚛𝚒𝚌𝚝𝚕𝚢_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ constraint

Figure 5.380.2. Automaton of the $𝚜𝚝𝚛𝚒𝚌𝚝𝚕𝚢_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ constraint

Figure 5.380.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚜𝚝𝚛𝚒𝚌𝚝𝚕𝚢_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.380. strictly_increasing

Figure 5.380.1. Initial and final graph of the 𝚜𝚝𝚛𝚒𝚌𝚝𝚕𝚢_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐 constraint

Figure 5.380.2. Automaton of the 𝚜𝚝𝚛𝚒𝚌𝚝𝚕𝚢_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐 constraint

Figure 5.380.3. Hypergraph of the reformulation corresponding to the automaton of the 𝚜𝚝𝚛𝚒𝚌𝚝𝚕𝚢_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐 constraint

Figure 5.380.1. Initial and final graph of the $𝚜𝚝𝚛𝚒𝚌𝚝𝚕𝚢_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ constraint

Figure 5.380.2. Automaton of the $𝚜𝚝𝚛𝚒𝚌𝚝𝚕𝚢_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ constraint

Figure 5.380.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚜𝚝𝚛𝚒𝚌𝚝𝚕𝚢_𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ constraint