5.110. decreasing

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Inspired by πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš.

Constraint

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

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

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

Example
(8,4,1,1)

The πšπšŽπšŒπš›πšŽπšŠπšœπš’πš—πš constraint holds since 8β‰₯4β‰₯1β‰₯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)2345678
Solutions62070252924343212870

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.

See also

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

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
π‘ƒπ΄π‘‡π»β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

Arc arity
Arc constraint(s)
πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›β‰₯πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ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
ctrs/decreasingActrs/decreasingB
(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 β‰₯πš…π™°πš i+1 ⇔S i .

Figure 5.110.2. Automaton of the πšπšŽπšŒπš›πšŽπšŠπšœπš’πš—πš constraint
ctrs/decreasing-3-tikz
Figure 5.110.3. Hypergraph of the reformulation corresponding to the automaton of the πšπšŽπšŒπš›πšŽπšŠπšœπš’πš—πš constraint
ctrs/decreasing-4-tikz