5.219. minimum_greater_than

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

N.Β Beldiceanu

Constraint

πš–πš’πš—πš’πš–πšžπš–_πšπš›πšŽπšŠπšπšŽπš›_πšπš‘πšŠπš—(πš…π™°πš1,πš…π™°πš2,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

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

πš…π™°πš1 is the smallest value strictly greater than πš…π™°πš2 of the collection of variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚: this concretely means that there exists at least one variable of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ that takes a value strictly greater than πš…π™°πš2.

Example
(5,3,8,5,3,8)

The πš–πš’πš—πš’πš–πšžπš–_πšπš›πšŽπšŠπšπšŽπš›_πšπš‘πšŠπš— constraint holds since value 5 is the smallest value strictly greater than value 3 among values 8,5,3 and 8.

Symmetry

Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are permutable.

Reformulation

Let V 1 ,V 2 ,...,V |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚| denote the variables of the collection of variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚. By creating the extra variables M and U 1 ,U 2 ,...,U |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚| , the πš–πš’πš—πš’πš–πšžπš–_πšπš›πšŽπšŠπšπšŽπš›_πšπš‘πšŠπš— constraint can be expressed in term of the following constraints:

  1. πš–πšŠπš‘πš’πš–πšžπš–(M,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚),

  2. πš…π™°πš1>πš…π™°πš2,

  3. πš…π™°πš1≀M,

  4. V i β‰€πš…π™°πš2β‡’U i =M (i∈[1,|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|]),

  5. V i >πš…π™°πš2β‡’U i =V i (i∈[1,|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|]),

  6. πš–πš’πš—πš’πš–πšžπš–(πš…π™°πš1,〈U 1 ,U 2 ,...,U |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚| βŒͺ).

See also

common keyword: πš—πšŽπš‘πš_πšπš›πšŽπšŠπšπšŽπš›_πšŽπš•πšŽπš–πšŽπš—πšΒ (order constraint).

related: πš—πšŽπš‘πš_πšŽπš•πšŽπš–πšŽπš—πšΒ (identify an element in a table).

Keywords

characteristic of a constraint: minimum, automaton, automaton without counters, reified automaton constraint, derived collection.

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

constraint type: order constraint.

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

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

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

Arc arity
Arc constraint(s)
πš’πšπšŽπš–.πšŸπšŠπš›<πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ.πšŸπšŠπš›
Graph property(ies)
𝐍𝐀𝐑𝐂>0

Sets
𝖲𝖴𝖒𝖒↦[πšœπš˜πšžπš›πšŒπšŽ,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ]

Constraint(s) on sets
πš–πš’πš—πš’πš–πšžπš–(πš…π™°πš1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ)
Graph model

Similar to the πš—πšŽπš‘πš_πšπš›πšŽπšŠπšπšŽπš›_πšŽπš•πšŽπš–πšŽπš—πš constraint, except that there is no order on the variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.

PartsΒ (A) andΒ (B) of FigureΒ 5.219.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. The source and the sinks of the final graph respectively correspond to the variable πš…π™°πš2 and to the variables of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection that are strictly greater than πš…π™°πš2. πš…π™°πš1 is set to the smallest value of the πšŸπšŠπš› attribute of the sinks of the final graph.

Figure 5.219.1. Initial and final graph of the πš–πš’πš—πš’πš–πšžπš–_πšπš›πšŽπšŠπšπšŽπš›_πšπš‘πšŠπš— constraint
ctrs/minimum_greater_thanActrs/minimum_greater_thanB
(a) (b)
Automaton

FigureΒ 5.219.2 depicts the automaton associated with the πš–πš’πš—πš’πš–πšžπš–_πšπš›πšŽπšŠπšπšŽπš›_πšπš‘πšŠπš— constraint. Let πš…π™°πš i be the i th variable of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection. To each triple (πš…π™°πš1,πš…π™°πš2,πš…π™°πš i ) corresponds a signature variable πš‚ i as well as the following signature constraint:

((πš…π™°πš i <πš…π™°πš1)∧(πš…π™°πš i β‰€πš…π™°πš2))β‡”πš‚ i =0 ∧

((πš…π™°πš i =πš…π™°πš1)∧(πš…π™°πš i β‰€πš…π™°πš2))β‡”πš‚ i =1 ∧

((πš…π™°πš i >πš…π™°πš1)∧(πš…π™°πš i β‰€πš…π™°πš2))β‡”πš‚ i =2 ∧

((πš…π™°πš i <πš…π™°πš1)∧(πš…π™°πš i >πš…π™°πš2))β‡”πš‚ i =3 ∧

((πš…π™°πš i =πš…π™°πš1)∧(πš…π™°πš i >πš…π™°πš2))β‡”πš‚ i =4 ∧

((πš…π™°πš i >πš…π™°πš1)∧(πš…π™°πš i >πš…π™°πš2))β‡”πš‚ i =5.

The automaton is constructed in order to fulfil the following conditions:

  • We look for an item of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection such that πšŸπšŠπš› i =πš…π™°πš1 and πšŸπšŠπš› i >πš…π™°πš2,

  • There should not exist any item of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection such that πšŸπšŠπš› i <πš…π™°πš1 and πšŸπšŠπš› i >πš…π™°πš2.

Figure 5.219.2. Automaton of the πš–πš’πš—πš’πš–πšžπš–_πšπš›πšŽπšŠπšπšŽπš›_πšπš‘πšŠπš— constraint
ctrs/minimum_greater_than1
Figure 5.219.3. Hypergraph of the reformulation corresponding to the automaton of the πš–πš’πš—πš’πš–πšžπš–_πšπš›πšŽπšŠπšπšŽπš›_πšπš‘πšŠπš— constraint
ctrs/minimum_greater_than2