5.228. next_greater_element

DESCRIPTIONLINKSGRAPH
Origin

M.Β Carlsson

Constraint

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

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

πš…π™°πš2 is the value strictly greater than πš…π™°πš1 located at the smallest possible entry of the table πšƒπ™°π™±π™»π™΄. In addition, the variables of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are sorted in strictly increasing order.

Example
(7,8,3,5,8,9)

The πš—πšŽπš‘πš_πšπš›πšŽπšŠπšπšŽπš›_πšŽπš•πšŽπš–πšŽπš—πš constraint holds since:

  • πš…π™°πš2 is fixed to the first value 8 strictly greater than πš…π™°πš1=7,

  • The πšŸπšŠπš› attributes of the items of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ are sorted in strictly increasing order.

Usage

Originally introduced inΒ [CarlssonBeldiceanu04] for modelling the fact that a nucleotide has to be consumed as soon as possible at cycle πš…π™°πš2 after a given cycle πš…π™°πš1.

Remark

Similar to the πš–πš’πš—πš’πš–πšžπš–_πšπš›πšŽπšŠπšπšŽπš›_πšπš‘πšŠπš— constraint, except for the fact that the πšŸπšŠπš› attributes are sorted.

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. V 1 <V 2 <...<V |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|

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

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

  4. πš…π™°πš2≀M,

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

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

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

See also

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

related: πš—πšŽπš‘πš_πšŽπš•πšŽπš–πšŽπš—πšΒ (allow to iterate over the values of a table).

Keywords

characteristic of a constraint: minimum, derived collection.

constraint type: order constraint, data constraint.

modelling: table.

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

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

Arc generator
π‘ƒπ΄π‘‡π»β†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

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

Arc input(s)

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

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

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

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

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

PartsΒ (A) andΒ (B) of FigureΒ 5.228.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 arcs of the final graph are stressed in bold.

Figure 5.228.1. Initial and final graph of the πš—πšŽπš‘πš_πšπš›πšŽπšŠπšπšŽπš›_πšŽπš•πšŽπš–πšŽπš—πš constraint
ctrs/next_greater_elementActrs/next_greater_elementB
(a) (b)
Signature

Since the first graph constraint uses the 𝑃𝐴𝑇𝐻 arc generator on the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection, the number of arcs of the corresponding initial graph is equal to |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-1. Therefore the maximum number of arcs of the final graph is equal to |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-1. For this reason we can rewrite 𝐍𝐀𝐑𝐂=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-1 to 𝐍𝐀𝐑𝐂β‰₯|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-1 and simplify 𝐍𝐀𝐑𝐂 Β― Μ² to 𝐍𝐀𝐑𝐂 Β―.