5.207. max_n

DESCRIPTIONLINKSGRAPH
Origin

[Beldiceanu01]

Constraint

πš–πšŠπš‘_πš—(π™Όπ™°πš‡,πšπ™°π™½π™Ί,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

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

π™Όπ™°πš‡ is the maximum value of rank πšπ™°π™½π™Ί (i.e.,Β the πšπ™°π™½π™Ί th largest distinct value) of the collection of domain variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚. Sinks have a rank of 0.

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

The πš–πšŠπš‘_πš— constraint holds since its first argument π™Όπ™°πš‡=6 is fixed to the second (i.e.,Β πšπ™°π™½π™Ί+1) largest distinct value of the collection 〈3,1,7,1,6βŒͺ.

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

By associating to each variable V i (i∈[1,|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|]) of the πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ collection a rank variable R i with the reified constraint R i =πšπ™°π™½π™Ίβ‡”V 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 maximum replaced by maximum or order πš—).

Keywords

characteristic of a constraint: rank, maximum.

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.207.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 outlined with a thick circle.

Figure 5.207.1. Initial and final graph of the πš–πšŠπš‘_πš— constraint
ctrs/max_nActrs/max_nB
(a) (b)