Global Constraint Catalog: Cdecreasing

5.110. decreasing

DESCRIPTION

LINKS

GRAPH

AUTOMATON

Origin

Inspired by $𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ .

Constraint

$𝚍𝚎𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐 (𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂)$

Argument

𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂

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

Restriction

𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍

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

Purpose

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

Example

(〈8, 4, 1, 1〉)

The $𝚍𝚎𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ constraint holds since $8 \geq 4 \geq 1 \geq 1$ .

Typical

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

𝚛𝚊𝚗𝚐𝚎

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

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
Solutions	6	20	70	252	924	3432	12870

Number of solutions for $𝚍𝚎𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ : domains $0 . . n$

ctrs/decreasing-1-tikz

ctrs/decreasing-2-tikz

Systems

increasingNValue in Choco, rel in Gecode, decreasing in MiniZinc.

comparison swapped: $𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ .

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

implies: $𝚖𝚞𝚕𝚝𝚒_𝚐𝚕𝚘𝚋𝚊𝚕_𝚌𝚘𝚗𝚝𝚒𝚐𝚞𝚒𝚝𝚢$ , $𝚗𝚘_𝚙𝚎𝚊𝚔$ , $𝚗𝚘_𝚟𝚊𝚕𝚕𝚎𝚢$ .

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.

final graph structure: acyclic, bipartite, no loop.

Arc input(s)

$𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂$

Arc generator

𝑃𝐴𝑇𝐻

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

Arc arity

Arc constraint(s)

𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 1 . 𝚟𝚊𝚛 \geq 𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜 2 . 𝚟𝚊𝚛

Graph property(ies)

𝐍𝐀𝐑𝐂

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

Graph class

•

𝙰𝙲𝚈𝙲𝙻𝙸𝙲

•

𝙱𝙸𝙿𝙰𝚁𝚃𝙸𝚃𝙴

•

𝙽𝙾_𝙻𝙾𝙾𝙿

Graph model

Parts (A) and (B) of Figure 5.110.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.110.1. Initial and final graph of the $𝚍𝚎𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ constraint


(a)	(b)

Automaton: Figure 5.110.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.110.2. Automaton of the $𝚍𝚎𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ constraint

Figure 5.110.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚍𝚎𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.110. decreasing

Figure 5.110.1. Initial and final graph of the $𝚍𝚎𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ constraint

Figure 5.110.2. Automaton of the $𝚍𝚎𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ constraint

Figure 5.110.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚍𝚎𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ constraint

Global Constraint Catalog

5. Global Constraint Catalogue

5.110. decreasing

Figure 5.110.1. Initial and final graph of the 𝚍𝚎𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐 constraint

Figure 5.110.2. Automaton of the 𝚍𝚎𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐 constraint

Figure 5.110.3. Hypergraph of the reformulation corresponding to the automaton of the 𝚍𝚎𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐 constraint

Figure 5.110.1. Initial and final graph of the $𝚍𝚎𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ constraint

Figure 5.110.2. Automaton of the $𝚍𝚎𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ constraint

Figure 5.110.3. Hypergraph of the reformulation corresponding to the automaton of the $𝚍𝚎𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐$ constraint