## 5.142. global_cardinality_with_costs

 DESCRIPTION LINKS GRAPH
Origin
Constraint

$\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚠𝚒𝚝𝚑}_\mathrm{𝚌𝚘𝚜𝚝𝚜}\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂},\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇},\mathrm{𝙲𝙾𝚂𝚃}\right)$

Synonyms

$\mathrm{𝚐𝚌𝚌𝚌}$, $\mathrm{𝚌𝚘𝚜𝚝}_\mathrm{𝚐𝚌𝚌}$.

Arguments
 $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛}-\mathrm{𝚍𝚟𝚊𝚛}\right)$ $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚕}-\mathrm{𝚒𝚗𝚝},\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}-\mathrm{𝚍𝚟𝚊𝚛}\right)$ $\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}$ $\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(𝚒-\mathrm{𝚒𝚗𝚝},𝚓-\mathrm{𝚒𝚗𝚝},𝚌-\mathrm{𝚒𝚗𝚝}\right)$ $\mathrm{𝙲𝙾𝚂𝚃}$ $\mathrm{𝚍𝚟𝚊𝚛}$
Restrictions
 $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚟𝚊𝚛}\right)$ $|\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}|>0$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂},\left[\mathrm{𝚟𝚊𝚕},\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}\right]\right)$ $\mathrm{𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝}$$\left(\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂},\mathrm{𝚟𝚊𝚕}\right)$ $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}\ge 0$ $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}\le |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$ $\mathrm{𝚛𝚎𝚚𝚞𝚒𝚛𝚎𝚍}$$\left(\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇},\left[𝚒,𝚓,𝚌\right]\right)$ $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}_\mathrm{𝚜𝚎𝚚}$$\left(\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇},\left[𝚒,𝚓\right]\right)$ $\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}.𝚒\ge 1$ $\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}.𝚒\le |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|$ $\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}.𝚓\ge 1$ $\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}.𝚓\le |\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}|$ $|\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}|=|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|*|\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}|$
Purpose

Each value $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\left[i\right].\mathrm{𝚟𝚊𝚕}$ should be taken by exactly $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\left[i\right].\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}$ variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection. In addition the $\mathrm{𝙲𝙾𝚂𝚃}$ of an assignment is equal to the sum of the elementary costs associated with the fact that we assign the ${i}^{th}$ variable of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection to the ${j}^{th}$ value of the $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ collection. These elementary costs are given by the $\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}$ collection.

Example
$\left(\begin{array}{c}〈3,3,3,6〉,\hfill \\ 〈\begin{array}{cc}\mathrm{𝚟𝚊𝚕}-3\hfill & \mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}-3,\hfill \\ \mathrm{𝚟𝚊𝚕}-5\hfill & \mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}-0,\hfill \\ \mathrm{𝚟𝚊𝚕}-6\hfill & \mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}-1\hfill \end{array}〉,\hfill \\ 〈\begin{array}{ccc}𝚒-1\hfill & 𝚓-1\hfill & 𝚌-4,\hfill \\ 𝚒-1\hfill & 𝚓-2\hfill & 𝚌-1,\hfill \\ 𝚒-1\hfill & 𝚓-3\hfill & 𝚌-7,\hfill \\ 𝚒-2\hfill & 𝚓-1\hfill & 𝚌-1,\hfill \\ 𝚒-2\hfill & 𝚓-2\hfill & 𝚌-0,\hfill \\ 𝚒-2\hfill & 𝚓-3\hfill & 𝚌-8,\hfill \\ 𝚒-3\hfill & 𝚓-1\hfill & 𝚌-3,\hfill \\ 𝚒-3\hfill & 𝚓-2\hfill & 𝚌-2,\hfill \\ 𝚒-3\hfill & 𝚓-3\hfill & 𝚌-1,\hfill \\ 𝚒-4\hfill & 𝚓-1\hfill & 𝚌-0,\hfill \\ 𝚒-4\hfill & 𝚓-2\hfill & 𝚌-0,\hfill \\ 𝚒-4\hfill & 𝚓-3\hfill & 𝚌-6\hfill \end{array}〉,14\hfill \end{array}\right)$

The $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚠𝚒𝚝𝚑}_\mathrm{𝚌𝚘𝚜𝚝𝚜}$ constraint holds since:

• Values 3, 5 and 6 respectively occur 3, 0 and 1 times within the collection $〈3,3,3,6〉$.

• The $\mathrm{𝙲𝙾𝚂𝚃}$ argument corresponds to the sum of the costs respectively associated with the first, second, third and fourth items of $〈3,3,3,6〉$, namely 4, 1, 3 and 6.

Typical
 $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>1$ $\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}.\mathrm{𝚟𝚊𝚛}\right)>1$ $|\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}|>1$ $\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}\right)>1$ $\mathrm{𝚛𝚊𝚗𝚐𝚎}$$\left(\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}.𝚌\right)>1$ $|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|>|\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}|$
Usage

A classical utilisation of the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚠𝚒𝚝𝚑}_\mathrm{𝚌𝚘𝚜𝚝𝚜}$ constraint corresponds to the following assignment problem. We have a set of persons $𝒫$ as well as a set of jobs $𝒥$ to perform. Each job requires a number of persons restricted to a specified interval. In addition each person $p$ has to be assigned to one specific job taken from a subset ${𝒥}_{p}$ of $𝒥$. There is a cost ${C}_{pj}$ associated with the fact that person $p$ is assigned to job $j$. The previous problem is modelled with one single $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚠𝚒𝚝𝚑}_\mathrm{𝚌𝚘𝚜𝚝𝚜}$ constraint where the persons and the jobs respectively correspond to the items of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ and $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ collection.

The $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚠𝚒𝚝𝚑}_\mathrm{𝚌𝚘𝚜𝚝𝚜}$ constraint can also be used for modelling a conjunction $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$$\left({𝚇}_{\mathtt{1}},{𝚇}_{\mathtt{2}},...,{𝚇}_{𝚗}\right)$ and ${\alpha }_{1}·{𝚇}_{\mathtt{1}}+{\alpha }_{2}·{𝚇}_{\mathtt{2}}+...+{\alpha }_{n}·{𝚇}_{𝚗}=\mathrm{𝙲𝙾𝚂𝚃}$. For this purpose we set the domain of the $\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}$ variables to $\left\{0,1\right\}$ and the cost attribute $𝚌$ of a variable ${𝚇}_{𝚒}$ and one of its potential value $𝚓$ to ${\alpha }_{i}·𝚓$. In practice this can be used for the magic squares and the magic hexagon problems where all the ${\alpha }_{i}$ are set to 1.

Algorithm
Reformulation

Let $n$ and $m$ respectively denote the number of items of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ and of the $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ collections. Let ${v}_{1},{v}_{2},...,{v}_{m}$ denote the values $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\left[1\right].\mathrm{𝚟𝚊𝚕},\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\left[2\right].\mathrm{𝚟𝚊𝚕},...,\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\left[m\right].\mathrm{𝚟𝚊𝚕}$. In addition let ${\mathrm{𝐿𝐼𝑁𝐸}}_{i}$ $\left(1\le i\le n\right)$ denote the values $〈\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}\left[m·\left(i-1\right)+1\right].𝚌,\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}\left[m·\left(i-1\right)+2\right].𝚌,...,\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}\left[m·i\right].𝚌〉$, i.e., the $i$-th line of the matrix $\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}$.

By introducing $2·n$ auxiliary variables ${U}_{1},{U}_{2},...,{U}_{n}$ and ${C}_{1},{C}_{2},...,{C}_{n}$, the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚠𝚒𝚝𝚑}_\mathrm{𝚌𝚘𝚜𝚝𝚜}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂},\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇},\mathrm{𝙲𝙾𝚂𝚃}\right)$ constraint can be expressed in term of the conjunction of one $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$$\left(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\right)$ constraint, $2·n$ $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$ constraints and one arithmetic constraint $\mathrm{𝚜𝚞𝚖}_\mathrm{𝚌𝚝𝚛}$.

For each variable ${V}_{i}$ $\left(1\le i\le |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}|\right)$ of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection a first $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$\left({U}_{i},〈{v}_{1},{v}_{2},...,{v}_{m}〉,{V}_{i}\right)$ constraint provides the correspondence between the variable ${V}_{i}$ and the index of the value ${U}_{i}$ to which it is assigned. A second $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$\left({U}_{i},{\mathrm{𝐿𝐼𝑁𝐸}}_{i},{C}_{i}\right)$ links the previous index ${U}_{i}$ to the cost ${C}_{i}$ variable associated with variable ${V}_{i}$. Finally the total cost $\mathrm{𝙲𝙾𝚂𝚃}$ is equal to the sum ${C}_{1}+{C}_{2}+...+{C}_{n}$.

In the context of the Example slot we get the following conjunction of constraints:

$\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$$\left(〈3,3,3,6〉,$

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

$\mathrm{𝚟𝚊𝚕}-5\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}-0,$

$\mathrm{𝚟𝚊𝚕}-6\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}-1〉\right)$,

$\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$\left(1,〈3,5,6〉,3\right)$,

$\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$\left(1,〈3,5,6〉,3\right)$,

$\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$\left(1,〈3,5,6〉,3\right)$,

$\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$\left(3,〈3,5,6〉,6\right)$,

$\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$\left(1,〈4,1,7〉,4\right)$,

$\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$\left(1,〈1,0,8〉,1\right)$,

$\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$\left(1,〈3,2,1〉,3\right)$,

$\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$\left(3,〈0,0,6〉,6\right)$,

$14=4+1+3+6$.

Systems
See also

attached to cost variant: $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ ($\mathrm{𝚌𝚘𝚜𝚝}$ associated with each $\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎}$,$\mathrm{𝚟𝚊𝚕𝚞𝚎}$ pair removed).

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{𝐍𝐕𝐄𝐑𝐓𝐄𝐗}$$=\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}$

Arc input(s)

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

Arc generator
$\mathrm{𝑃𝑅𝑂𝐷𝑈𝐶𝑇}$$↦\mathrm{𝚌𝚘𝚕𝚕𝚎𝚌𝚝𝚒𝚘𝚗}\left(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜},\mathrm{𝚟𝚊𝚕𝚞𝚎𝚜}\right)$

Arc arity
Arc constraint(s)
$\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}.\mathrm{𝚟𝚊𝚛}=\mathrm{𝚟𝚊𝚕𝚞𝚎𝚜}.\mathrm{𝚟𝚊𝚕}$
Graph property(ies)
$\mathrm{𝐒𝐔𝐌}_\mathrm{𝐖𝐄𝐈𝐆𝐇𝐓}_\mathrm{𝐀𝐑𝐂}$$\left(\begin{array}{c}\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}\left[\left(\mathrm{𝚟𝚊𝚛𝚒𝚊𝚋𝚕𝚎𝚜}.\mathrm{𝚔𝚎𝚢}-1\right)*|\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}|+\mathrm{𝚟𝚊𝚕𝚞𝚎𝚜}.\mathrm{𝚔𝚎𝚢}\right].𝚌\hfill \end{array}\right)=\mathrm{𝙲𝙾𝚂𝚃}$

Graph model

The first graph constraint enforces each value of the $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ collection to be taken by a specific number of variables of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection. It is identical to the graph constraint used in the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$ constraint. The second graph constraint expresses the fact that the $\mathrm{𝙲𝙾𝚂𝚃}$ variable is equal to the sum of the elementary costs associated with each variable -value assignment. All these elementary costs are recorded in the $\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}$ collection. More precisely, the cost ${c}_{ij}$ is recorded in the attribute $𝚌$ of the ${\left(\left(i-1\right)·|\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\right)|+j\right)}^{th}$ entry of the $\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}$ collection. This is ensured by the $\mathrm{𝚒𝚗𝚌𝚛𝚎𝚊𝚜𝚒𝚗𝚐}$ restriction that enforces the fact that the items of the $\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}$ collection are sorted in lexicographically increasing order according to attributes $𝚒$ and $𝚓$.

Parts (A) and (B) of Figure 5.142.1 respectively show the initial and final graph associated with the second graph constraint of the Example slot.

##### Figure 5.142.1. Initial and final graph of the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}_\mathrm{𝚠𝚒𝚝𝚑}_\mathrm{𝚌𝚘𝚜𝚝𝚜}$ constraint  (a) (b)