## 5.139. global_cardinality_low_up

Origin
Constraint

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

Synonyms

$\mathrm{𝚐𝚌𝚌}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$, $\mathrm{𝚐𝚌𝚌}$.

Arguments
 $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$ $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚕}-\mathrm{𝚒𝚗𝚝},\mathrm{𝚘𝚖𝚒𝚗}-\mathrm{𝚒𝚗𝚝},\mathrm{𝚘𝚖𝚊𝚡}-\mathrm{𝚒𝚗𝚝}\right)$
Restrictions
 $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚟𝚊𝚛}\right)$ $|\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}|>0$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂},\left[\mathrm{𝚟𝚊𝚕},\mathrm{𝚘𝚖𝚒𝚗},\mathrm{𝚘𝚖𝚊𝚡}\right]\right)$ $\mathrm{𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝}$$\left(\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂},\mathrm{𝚟𝚊𝚕}\right)$ $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚘𝚖𝚒𝚗}\ge 0$ $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚘𝚖𝚊𝚡}\le |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$ $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚘𝚖𝚒𝚗}\le \mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚘𝚖𝚊𝚡}$
Purpose

Each value $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\left[i\right].\mathrm{𝚟𝚊𝚕}$ $\left(1\le i\le |\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}|\right)$ should be taken by at least $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\left[i\right].\mathrm{𝚘𝚖𝚒𝚗}$ and at most $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\left[i\right].\mathrm{𝚘𝚖𝚊𝚡}$ variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection.

Example
$\left(\begin{array}{c}〈3,3,8,6〉,\hfill \\ 〈\begin{array}{ccc}\mathrm{𝚟𝚊𝚕}-3\hfill & \mathrm{𝚘𝚖𝚒𝚗}-2\hfill & \mathrm{𝚘𝚖𝚊𝚡}-3,\hfill \\ \mathrm{𝚟𝚊𝚕}-5\hfill & \mathrm{𝚘𝚖𝚒𝚗}-0\hfill & \mathrm{𝚘𝚖𝚊𝚡}-1,\hfill \\ \mathrm{𝚟𝚊𝚕}-6\hfill & \mathrm{𝚘𝚖𝚒𝚗}-1\hfill & \mathrm{𝚘𝚖𝚊𝚡}-2\hfill \end{array}〉\hfill \end{array}\right)$

The $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$ constraint holds since values 3, 5 and 6 are respectively used 2 ($2\le 2\le 3$), 0 ($0\le 0\le 1$) and 1 ($1\le 1\le 2$) times within the collection $〈3,3,8,6〉$ and since no constraint was specified for value 8.

Typical
 $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>1$ $\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}\right)>1$ $|\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}|>1$ $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚘𝚖𝚒𝚗}\le |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$ $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚘𝚖𝚊𝚡}>0$ $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚘𝚖𝚊𝚡}\le |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$ $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>|\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}|$
Symmetries
• Items of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ are permutable.

• An occurrence of a value of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}$ that does not belong to $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚟𝚊𝚕}$ can be replaced by any other value that also does not belong to $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚟𝚊𝚕}$.

• Items of $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ are permutable.

• $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚘𝚖𝚒𝚗}$ can be decreased to any value $\ge 0$.

• $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚘𝚖𝚊𝚡}$ can be increased to any value $\le |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$.

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

Remark

Within the context of linear programming [Hooker07book] provides relaxations of the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$ constraint.

Algorithm

A filtering algorithm achieving arc-consistency for the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$ constraint is given in [Regin96].

The $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$ constraint is entailed if and only if for each value $v$ equal to $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\left[i\right].\mathrm{𝚟𝚊𝚕}$ (with $1\le i\le |\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}|$) the following two conditions hold:

1. The number of variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection assigned value $v$ is greater than or equal to $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\left[i\right].\mathrm{𝚘𝚖𝚒𝚗}$.

2. The number of variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection that can potentially be assigned value $v$ is less than or equal to $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\left[i\right].\mathrm{𝚘𝚖𝚊𝚡}$.

Reformulation

A reformulation of the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$, involving linear constraints, preserving bound-consistency was introduced in [BessiereKatsirelosNarodytskaQuimperWalsh09IJCAI]. For each potential interval $\left[l,u\right]$ of consecutive values this model uses $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$ 0-1 variables ${B}_{1,l,u},{B}_{2,l,u},...,{B}_{|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|,l,u}$ for modelling the fact that each variable of the collection $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ is assigned a value within interval $\left[l,u\right]$ (i.e., $\forall i\in \left[1,|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|\right]:{B}_{i,l,u}⇔l\le \mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\left[i\right].\mathrm{𝚟𝚊𝚛}\wedge \mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\left[i\right].\mathrm{𝚟𝚊𝚛}\le u$), as well as one domain variable ${C}_{l,u}$ for counting how many values of $\left[l,u\right]$ are assigned to variables of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ (i.e. ${C}_{l,u}={B}_{1,l,u}+{B}_{2,l,u}+...+{B}_{|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|,l,u}$). The lower and upper bounds of variable ${C}_{l,u}$ are respectively initially set with respect to the minimum and maximum number of possible occurrences of the values of interval $\left[l,u\right]$. Finally, assuming that $s$ is the smallest value that can be assigned to the variables of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$, the constraint ${C}_{s,u}={C}_{s,k}+{C}_{k+1,u}$ is stated for each $k\in \left[s,u-1\right]$.

Systems
Used in

generalisation: $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ ($\mathrm{𝚏𝚒𝚡𝚎𝚍}$ $\mathrm{𝚒𝚗𝚝𝚎𝚛𝚟𝚊𝚕}$ replaced by $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$).

implied by: $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}_\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ (a $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$ constraint where the $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}$ are increasing), $\mathrm{𝚜𝚊𝚖𝚎}_\mathrm{𝚊𝚗𝚍}_\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$.

related: $\mathrm{𝚘𝚛𝚍𝚎𝚛𝚎𝚍}_\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ (restrictions are done on nested sets of values, all starting from first value).

shift of concept: $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}_\mathrm{𝚗𝚘}_\mathrm{𝚕𝚘𝚘𝚙}$ (assignment of a $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$ to its position is ignored).

soft variant: $\mathrm{𝚘𝚙𝚎𝚗}_\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$ (a $\mathrm{𝚜𝚎𝚝}$ $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$ defines the set of variables that are actually considered).

specialisation: $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ (each value should occur at most once).

system of constraints: $\mathrm{𝚜𝚕𝚒𝚍𝚒𝚗𝚐}_\mathrm{𝚍𝚒𝚜𝚝𝚛𝚒𝚋𝚞𝚝𝚒𝚘𝚗}$ (one $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚕𝚘𝚠}_\mathrm{𝚞𝚙}$ constraint for each sliding sequence of $\mathrm{𝚂𝙴𝚀}$ consecutive $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}$).

Keywords

For all items of $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$:

Arc input(s)

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

Arc generator
$\mathrm{𝑆𝐸𝐿𝐹}$$↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}\right)$

Arc arity
Arc constraint(s)
$\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}.\mathrm{𝚟𝚊𝚛}=\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚟𝚊𝚕}$
Graph property(ies)
 $•$$\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}$$\ge \mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚘𝚖𝚒𝚗}$ $•$$\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}$$\le \mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚘𝚖𝚊𝚡}$

Graph model

Since we want to express one unary constraint for each value we use the “For all items of $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$” iterator. Part (A) of Figure 5.139.1 shows the initial graphs associated with each value 3, 5 and 6 of the $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ collection of the Example slot. Part (B) of Figure 5.139.1 shows the two corresponding final graphs respectively associated with values 3 and 6 that are both assigned to the variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection (since value 5 is not assigned to any variable of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection the final graph associated with value 5 is empty). Since we use the $\mathrm{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}$ graph property, the vertices of the final graphs are stressed in bold.