## 5.257. min_nvalue

Origin

N. Beldiceanu

Constraint

$\mathrm{𝚖𝚒𝚗}_\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}\left(\mathrm{𝙼𝙸𝙽},\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$

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

$\mathrm{𝙼𝙸𝙽}$ is the minimum number of times that the same value is taken by the variables of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

Example
 $\left(2,〈9,1,7,1,1,7,7,7,7,9〉\right)$ $\left(5,〈8,8,8,8,8〉\right)$ $\left(2,〈1,8,1,8,1〉\right)$

In the first example, values $1,7,9$ are respectively used $3,5,2$ times. So the minimum number of time $\mathrm{𝙼𝙸𝙽}$ that a same value occurs is 2. Consequently the corresponding $\mathrm{𝚖𝚒𝚗}_\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$ constraint holds.

Typical
 $2*\mathrm{𝙼𝙸𝙽}\le |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$ $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>1$ $\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}\right)>1$
Symmetries
• Items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ are permutable.

• All occurrences of two distinct values of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}$ can be swapped; all occurrences of a value of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}$ can be renamed to any unused value.

Arg. properties

Functional dependency: $\mathrm{𝙼𝙸𝙽}$ determined by $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

Usage

This constraint may be used in order to replace a set of $\mathrm{𝚌𝚘𝚞𝚗𝚝}$ or $\mathrm{𝚊𝚖𝚘𝚗𝚐}$ constraints were one would have to generate explicitly one constraint for each potential value. Also useful for constraining the number of occurrences of the less used value without knowing this value in advance and without giving explicitly a lower limit on the number of occurrences of each value as it is done in the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint.

Reformulation

Assume that $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ is not empty. Let $\alpha$ and $\beta$ respectively denote the smallest and largest possible values that can be assigned to the variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection. Let the variables ${O}_{\alpha },{O}_{\alpha +1},\cdots ,{O}_{\beta }$ respectively correspond to the number of occurrences of values $\alpha ,\alpha +1,\cdots ,\beta$ within the variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection. The $\mathrm{𝚖𝚒𝚗}_\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$ constraint can be expressed as the conjunction of the following two constraints:

$\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ $\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},$

$〈\mathrm{𝚟𝚊𝚕}-\alpha \mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}-{O}_{\alpha },$

$\mathrm{𝚟𝚊𝚕}-\alpha +1\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}-{O}_{\alpha +1},$

$\cdots$

$\mathrm{𝚟𝚊𝚕}-\beta \mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}-{O}_{\beta }〉\right)$,

$\mathrm{𝚖𝚒𝚗}_𝚗$$\left(\mathrm{𝙼𝙸𝙽},1,〈0,{O}_{\alpha },{O}_{\alpha +1},\cdots ,{O}_{\beta }〉\right)$.

We use a $\mathrm{𝚖𝚒𝚗}_𝚗$ constraint (with its $\mathrm{𝚁𝙰𝙽𝙺}$ parameter set to 1) instead of a $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}$ constraint in order to discard the smallest value 0.

Counting
 Length ($n$) 2 3 4 5 6 7 8 Solutions 9 64 625 7776 117649 2097152 43046721

Number of solutions for $\mathrm{𝚖𝚒𝚗}_\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$: domains $0..n$

Length ($n$)2345678
Total9646257776117649209715243046721
 Parameter value

16605607470113442205872842473664
23-60300378036456566496
3-4--42019604032
4--5---2520
5---6---
6----7--
7-----8-
8------9

Solution count for $\mathrm{𝚖𝚒𝚗}_\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$: domains $0..n$

Keywords
Cond. implications

$\mathrm{𝚖𝚒𝚗}_\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}\left(\mathrm{𝙼𝙸𝙽},\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$

with  $\mathrm{𝙼𝙸𝙽}<|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$

implies $\mathrm{𝚊𝚝𝚕𝚎𝚊𝚜𝚝}_\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$$\left(\mathrm{𝙽𝚅𝙰𝙻},\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\right)$

when  $\mathrm{𝙽𝚅𝙰𝙻}=2$.

Arc input(s)

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

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

Arc arity
Arc constraint(s)
$\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{1}.\mathrm{𝚟𝚊𝚛}=\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\mathtt{2}.\mathrm{𝚟𝚊𝚛}$
Graph property(ies)
$\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐒𝐂𝐂}$$=\mathrm{𝙼𝙸𝙽}$

Graph model

Parts (A) and (B) of Figure 5.257.1 respectively show the initial and final graph associated with the first example of the Example slot. Since we use the $\mathrm{𝐌𝐈𝐍}_\mathrm{𝐍𝐒𝐂𝐂}$ graph property, we show the smallest strongly connected component of the final graph associated with the first example of the Example slot.

Automaton

Figure 5.257.2 depicts the automaton associated with the $\mathrm{𝚖𝚒𝚗}_\mathrm{𝚗𝚟𝚊𝚕𝚞𝚎}$ constraint. To each item of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ corresponds a signature variable ${S}_{i}$ that is equal to 0.