5.40. between_min_max

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

Used for defining πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ_πšŒπš˜πš—πšŸπšŽπš‘.

Constraint

πš‹πšŽπšπš πšŽπšŽπš—_πš–πš’πš—_πš–πšŠπš‘(πš…π™°πš,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

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

πš…π™°πš is greater than or equal to at least one variable of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ and less than or equal to at least one variable of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

Example
(3,1,1,4,8)

The πš‹πšŽπšπš πšŽπšŽπš—_πš–πš’πš—_πš–πšŠπš‘ constraint holds since its first argument 3 is greater than or equal to the minimum value of the values of the collection 〈1,1,4,8βŒͺ and less than or equal to the maximum value of 〈1,1,4,8βŒͺ.

Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>1
πš›πšŠπš—πšπšŽ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›)>1
Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are permutable.

  • πš…π™°πš can be set to any value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›.

Reformulation

By introducing two extra variables 𝙼𝙸𝙽 and π™Όπ™°πš‡, the πš‹πšŽπšπš πšŽπšŽπš—_πš–πš’πš—_πš–πšŠπš‘(πš…π™°πš,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚) constraint can be expressed in term of the following conjunction of constraints:

Β Β Β πš–πš’πš—πš’πš–πšžπš–(𝙼𝙸𝙽,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚),

Β Β Β πš–πšŠπš‘πš’πš–πšžπš–(π™Όπ™°πš‡,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚),

Β Β Β πš…π™°πšβ‰₯𝙼𝙸𝙽,

Β Β Β πš…π™°πšβ‰€π™Όπ™°πš‡.

Used in

πšŒπšžπš–πšžπš•πšŠπšπš’πšŸπšŽ_πšŒπš˜πš—πšŸπšŽπš‘.

See also

implied by: πš–πšŠπš‘πš’πš–πšžπš–, πš–πš’πš—πš’πš–πšžπš–.

Keywords

characteristic of a constraint: automaton, automaton without counters, reified automaton constraint.

constraint network structure: centered cyclic(1) constraint network(1).

Derived Collection
πšŒπš˜πš•(π™Έπšƒπ™΄π™Ό-πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›),[πš’πšπšŽπš–(πšŸπšŠπš›-πš…π™°πš)])
Arc input(s)

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

Arc generator
π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πšπšŽπš–,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ)

Arc arity
Arc constraint(s)
πš’πšπšŽπš–.πšŸπšŠπš›β‰₯πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›
Graph property(ies)
𝐍𝐀𝐑𝐂β‰₯1

Graph class
β€’ π™°π™²πšˆπ™²π™»π™Έπ™²
β€’ π™±π™Έπ™Ώπ™°πšπšƒπ™Έπšƒπ™΄
β€’ 𝙽𝙾_𝙻𝙾𝙾𝙿

Arc input(s)

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

Arc generator
π‘ƒπ‘…π‘‚π·π‘ˆπΆπ‘‡β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πš’πšπšŽπš–,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ)

Arc arity
Arc constraint(s)
πš’πšπšŽπš–.πšŸπšŠπš›β‰€πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›
Graph property(ies)
𝐍𝐀𝐑𝐂β‰₯1

Graph class
β€’ π™°π™²πšˆπ™²π™»π™Έπ™²
β€’ π™±π™Έπ™Ώπ™°πšπšƒπ™Έπšƒπ™΄
β€’ 𝙽𝙾_𝙻𝙾𝙾𝙿

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.40.1 respectively show the initial and final graph associated with the second graph constraint of the Example slot. Since we use the 𝐍𝐀𝐑𝐂 graph property, the two arcs of the final graph are stressed in bold. The constraint holds since 3 is greater than 1 and since 3 is less than 8.

Figure 5.40.1. Initial and final graph of the πš‹πšŽπšπš πšŽπšŽπš—_πš–πš’πš—_πš–πšŠπš‘ constraint
ctrs/between_min_maxActrs/between_min_maxB
(a) (b)
Automaton

FigureΒ 5.40.2 depicts the automaton associated with the πš‹πšŽπšπš πšŽπšŽπš—_πš–πš’πš—_πš–πšŠπš‘ constraint. To each pair (πš…π™°πš,πš…π™°πš i ), where πš…π™°πš i is a variable of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds a signature variable πš‚ i . The following signature constraint links πš…π™°πš, πš…π™°πš i and πš‚ i : (πš…π™°πš <πš…π™°πš i β‡”πš‚ i =0) ∧ (πš…π™°πš =πš…π™°πš i β‡”πš‚ i =1) ∧ (πš…π™°πš >πš…π™°πš i β‡”πš‚ i =2).

Figure 5.40.2. Automaton of the πš‹πšŽπšπš πšŽπšŽπš—_πš–πš’πš—_πš–πšŠπš‘ constraint
ctrs/between_min_max1
Figure 5.40.3. Hypergraph of the reformulation corresponding to the automaton of the πš‹πšŽπšπš πšŽπšŽπš—_πš–πš’πš—_πš–πšŠπš‘ constraint
ctrs/between_min_max2