5.321. strictly_decreasing

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Derived from πšœπšπš›πš’πšŒπšπš•πš’_πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš.

Constraint

πšœπšπš›πš’πšŒπšπš•πš’_πšπšŽπšŒπš›πšŽπšŠπšœπš’πš—πš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Argument
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restriction
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
Purpose

The variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are strictly decreasing.

Example
(8,4,3,1)

The πšœπšπš›πš’πšŒπšπš•πš’_πšπšŽπšŒπš›πšŽπšŠπšœπš’πš—πš constraint holds since 8>4>3>1.

Symmetry

One and the same constant can be added to the πšŸπšŠπš› attribute of all items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

Systems

increasingNValue in Choco, rel in Gecode.

See also

common keyword: πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πšΒ (order constraint).

comparison swapped: πšœπšπš›πš’πšŒπšπš•πš’_πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš.

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.

Arc input(s)

πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚

Arc generator
π‘ƒπ΄π‘‡π»β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›>πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›
Graph property(ies)
𝐍𝐀𝐑𝐂=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-1

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.321.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.321.1. Initial and final graph of the πšœπšπš›πš’πšŒπšπš•πš’_πšπšŽπšŒπš›πšŽπšŠπšœπš’πš—πš constraint
ctrs/strictly_decreasingActrs/strictly_decreasingB
(a) (b)
Automaton

FigureΒ 5.321.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 πš‚ i . The following signature constraint links πš…π™°πš i , πš…π™°πš i+1 and πš‚ i : πš…π™°πš i β‰€πš…π™°πš i+1 β‡”πš‚ i .

Figure 5.321.2. Automaton of the πšœπšπš›πš’πšŒπšπš•πš’_πšπšŽπšŒπš›πšŽπšŠπšœπš’πš—πš constraint
ctrs/strictly_decreasing1
Figure 5.321.3. Hypergraph of the reformulation corresponding to the automaton of the πšœπšπš›πš’πšŒπšπš•πš’_πšπšŽπšŒπš›πšŽπšŠπšœπš’πš—πš constraint
ctrs/strictly_decreasing2