5.185. increasing

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

KOALOG

Constraint

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

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

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

Example
(1,1,4,8)

The πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš constraint holds since 1≀1≀4≀8.

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/increasing-1-tikz

ctrs/increasing-2-tikz

Systems

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

Used in

πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™, πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’, πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πš—πšŸπšŠπš•πšžπšŽ, πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πšœπšžπš–, πš—πšŸπšŠπš•πšžπšŽ, πšœπšžπš–_πšŒπšπš›.

See also

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

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

implied by: πšŠπš•πš•_πšŽπššπšžπšŠπš•, πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’, πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πš—πšŸπšŠπš•πšžπšŽΒ (remove π™½πš…π™°π™» parameter from πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πš—πšŸπšŠπš•πšžπšŽ), πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πšœπšžπš–Β (remove πš‚πš„π™Ό parameter from πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš_πšœπšžπš–), πšœπšπš›πš’πšŒπšπš•πš’_πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš.

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

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

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.185.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.185.1. Initial and final graph of the πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš constraint
ctrs/increasingActrs/increasingB
(a) (b)
Automaton

FigureΒ 5.185.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.185.2. Automaton of the πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš constraint
ctrs/increasing-3-tikz
Figure 5.185.3. Hypergraph of the reformulation corresponding to the automaton of the πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš constraint
ctrs/increasing-4-tikz