5.214. min_n

DESCRIPTIONLINKSGRAPHAUTOMATON
Origin

[Beldiceanu01]

Constraint

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

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

𝙼𝙸𝙽 is the minimum value of rank πšπ™°π™½π™Ί (i.e.,Β the πšπ™°π™½π™Ί th smallest distinct value) of the collection of domain variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚. Sources have a rank of 0.

Example
(3,1,3,1,7,1,6)

The πš–πš’πš—_πš— constraint holds since its first argument 𝙼𝙸𝙽=3 is fixed to the second (i.e.,Β πšπ™°π™½π™Ί+1) smallest distinct value of the collection 〈3,1,7,1,6βŒͺ. Note that identical values are only counted once: this is why the minimum of order 1 is 3 instead of 1.

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

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

Algorithm

[Beldiceanu01].

Reformulation

The constraint πšŠπš–πš˜πš—πš_πšŸπšŠπš›(1,βŒ©π™Όπ™Έπ™½βŒͺ,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚) enforces 𝙼𝙸𝙽 to be assigned one of the values of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚. The constraint πš—πšŸπšŠπš•πšžπšŽ(π™½πš…π™°π™»,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚) provides a hand on the number of distinct values assigned to the variables of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚. By associating to each variable V i (i∈[1,|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|]) of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection a rank variable R i ∈[0,|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-1] with the reified constraint R i =πšπ™°π™½π™Ίβ‡”V i =𝙼𝙸𝙽, the inequality R i <π™½πš…π™°π™», and by creating for each pair of variables V i ,V j (i,j<i∈[1,|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|]) the reified constraints

Β Β Β V i <V j ⇔R i <R j ,

Β Β Β V i =V j ⇔R i =R j ,

Β Β Β V i >V j ⇔R i >R j ,

one can reformulate the πš–πš’πš—_πš— constraint in term of 3Β·|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|Β·(|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-1) 2+1 reified constraints.

See also

comparison swapped: πš–πšŠπš‘_πš—.

generalisation: πš–πš’πš—πš’πš–πšžπš–Β (absolute minimum replaced by minimum or order πš—).

used in reformulation: πšŠπš–πš˜πš—πš_πšŸπšŠπš›, πš—πšŸπšŠπš•πšžπšŽ.

Keywords

characteristic of a constraint: rank, minimum, maxint, automaton, automaton with array of counters.

constraint type: order constraint.

Arc input(s)

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

Arc generator
πΆπΏπΌπ‘„π‘ˆπΈβ†¦πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2)

Arc arity
Arc constraint(s)
β‹πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πš”πšŽπš’=πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πš”πšŽπš’,πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ1.πšŸπšŠπš›<πšŸπšŠπš›πš’πšŠπš‹πš•πšŽπšœ2.πšŸπšŠπš›
Graph property(ies)
πŽπ‘πƒπ„π‘(πšπ™°π™½π™Ί,π™Όπ™°πš‡π™Έπ™½πšƒ,πšŸπšŠπš›)=𝙼𝙸𝙽

Graph model

PartsΒ (A) andΒ (B) of FigureΒ 5.214.1 respectively show the initial and final graph associated with the Example slot. Since we use the πŽπ‘πƒπ„π‘ graph property, the vertex of rank 1 (without considering the loops) of the final graph is shown in grey.

Figure 5.214.1. Initial and final graph of the πš–πš’πš—_πš— constraint
ctrs/min_nActrs/min_nB
(a) (b)
Automaton

FigureΒ 5.214.2 depicts the automaton associated with the πš–πš’πš—_πš— constraint. FigureΒ 5.214.2 depicts the automaton associated with the πš–πš’πš—_πš— constraint. To each item of the collection πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ corresponds a signature variable πš‚ i that is equal to 1.

Figure 5.214.2. Automaton of the πš–πš’πš—_πš— constraint
ctrs/min_n1