5.159. 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
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
πš›πšŠπš—πšπšŽ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›)>1
Symmetry

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

Systems

increasingNValue in Choco, rel in Gecode.

Used in

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

See also

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

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

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

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

FigureΒ 5.159.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.159.2. Automaton of the πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš constraint
ctrs/increasing1
Figure 5.159.3. Hypergraph of the reformulation corresponding to the automaton of the πš’πš—πšŒπš›πšŽπšŠπšœπš’πš—πš constraint
ctrs/increasing2