## 5.207. max_n

Origin
Constraint

$\mathrm{𝚖𝚊𝚡}_𝚗\left(\mathrm{𝙼𝙰𝚇},\mathrm{𝚁𝙰𝙽𝙺},\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$

Arguments
 $\mathrm{𝙼𝙰𝚇}$ $\mathrm{𝚍𝚟𝚊𝚛}$ $\mathrm{𝚁𝙰𝙽𝙺}$ $\mathrm{𝚒𝚗𝚝}$ $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$
Restrictions
 $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>0$ $\mathrm{𝚁𝙰𝙽𝙺}\ge 0$ $\mathrm{𝚁𝙰𝙽𝙺}<|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚟𝚊𝚛}\right)$
Purpose

$\mathrm{𝙼𝙰𝚇}$ is the maximum value of rank $\mathrm{𝚁𝙰𝙽𝙺}$ (i.e., the ${\mathrm{𝚁𝙰𝙽𝙺}}^{th}$ largest distinct value) of the collection of domain variables $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$. Sinks have a rank of 0.

Example
$\left(6,1,〈3,1,7,1,6〉\right)$

The $\mathrm{𝚖𝚊𝚡}_𝚗$ constraint holds since its first argument $\mathrm{𝙼𝙰𝚇}=6$ is fixed to the second (i.e., $\mathrm{𝚁𝙰𝙽𝙺}+1$) largest distinct value of the collection $〈3,1,7,1,6〉$.

Symmetries
• Items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ are permutable.

• One and the same constant can be added to $\mathrm{𝙼𝙰𝚇}$ as well as to the $\mathrm{𝚟𝚊𝚛}$ attribute of all items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

Algorithm
Reformulation

By associating to each variable ${V}_{i}$ $\left(i\in \left[1,|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|\right]\right)$ of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection a rank variable ${R}_{i}$ with the reified constraint ${R}_{i}=\mathrm{𝚁𝙰𝙽𝙺}⇔{V}_{i}=\mathrm{𝙼𝙰𝚇}$, and by creating for each pair of variables ${V}_{i},{V}_{j}$ $\left(i,j 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 $\mathrm{𝚖𝚊𝚡}_𝚗$ constraint in term of $3·\frac{|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|·\left(|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|-1\right)}{2}+1$ reified constraints.

generalisation: $\mathrm{𝚖𝚊𝚡𝚒𝚖𝚞𝚖}$ (absolute maximum replaced by maximum or order $𝚗$).

Keywords
Arc input(s)

$\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$

Arc generator
$\mathrm{𝐶𝐿𝐼𝑄𝑈𝐸}$$↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1},\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}\right)$

Arc arity
Arc constraint(s)
$\bigvee \left(\begin{array}{c}\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1}.\mathrm{𝚔𝚎𝚢}=\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}.\mathrm{𝚔𝚎𝚢},\hfill \\ \mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1}.\mathrm{𝚟𝚊𝚛}>\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}.\mathrm{𝚟𝚊𝚛}\hfill \end{array}\right)$
Graph property(ies)
$\mathrm{𝐎𝐑𝐃𝐄𝐑}$$\left(\mathrm{𝚁𝙰𝙽𝙺},\mathrm{𝙼𝙸𝙽𝙸𝙽𝚃},\mathrm{𝚟𝚊𝚛}\right)=\mathrm{𝙼𝙰𝚇}$

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 $\mathrm{𝐎𝐑𝐃𝐄𝐑}$ graph property, the vertex of rank 1 (without considering the loops) of the final graph is outlined with a thick circle.