[Regin99a]

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

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

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

• Values 3, 5 and 6 respectively occur 3, 0 and 1 times within the collection $\langle 3,3,3,6\rangle$.

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

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{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$$({𝚇}_{\mathtt{1}},{𝚇}_{\mathtt{2}},...,{𝚇}_{𝚗})$ and ${\alpha }_1·{𝚇}_{\mathtt{1}}+{\alpha }_2·{𝚇}_{\mathtt{2}}+...+{\alpha }_n·{𝚇}_{𝚗}=\mathrm{𝙲𝙾𝚂𝚃}$. For this purpose we set the domain of the $\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}$ variables to $\{0,1\}$ 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.

[Regin99a], [Regin02]

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$ $(1\le i\le n)$ denote the values $\langle \mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}[m·(i-1)+1].𝚌,\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}[m·(i-1)+2].𝚌,...,\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}[m·i].𝚌\rangle$, 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{𝚌𝚘𝚜𝚝𝚜}$$(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂},\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇},\mathrm{𝙲𝙾𝚂𝚃})$ constraint can be expressed in term of the conjunction of one $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$$(\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂},\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂})$ constraint, $2·n$ $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$ constraints and one arithmetic constraint $\mathrm{𝚜𝚞𝚖}\_\mathrm{𝚌𝚝𝚛}$.

For each variable $V_i$ $(1\le i\le |\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\left|\right)$ of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection a first $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(U_i,\langle v_1,v_2,...,v_m\rangle ,V_i)$ 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{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(U_i,{\mathrm{𝐿𝐼𝑁𝐸}}_i,C_i)$ 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{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$$(\langle 3,3,3,6\rangle ,$

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

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

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

   $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(1,\langle 3,5,6\rangle ,3)$,

   $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(1,\langle 3,5,6\rangle ,3)$,

   $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(1,\langle 3,5,6\rangle ,3)$,

   $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(3,\langle 3,5,6\rangle ,6)$,

   $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(1,\langle 4,1,7\rangle ,4)$,

   $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(1,\langle 1,0,8\rangle ,1)$,

   $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(1,\langle 3,2,1\rangle ,3)$,

   $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(3,\langle 0,0,6\rangle ,6)$,

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

global_cardinality in SICStus.

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

common keyword: $\mathrm{𝚖𝚒𝚗𝚒𝚖𝚞𝚖}\_\mathrm{𝚠𝚎𝚒𝚐𝚑𝚝}\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ (cost filtering constraint,weighted assignment), $\mathrm{𝚜𝚞𝚖}\_\mathrm{𝚘𝚏}\_\mathrm{𝚠𝚎𝚒𝚐𝚑𝚝𝚜}\_\mathrm{𝚘𝚏}\_\mathrm{𝚍𝚒𝚜𝚝𝚒𝚗𝚌𝚝}\_\mathrm{𝚟𝚊𝚕𝚞𝚎𝚜}$, $\mathrm{𝚠𝚎𝚒𝚐𝚑𝚝𝚎𝚍}\_\mathrm{𝚙𝚊𝚛𝚝𝚒𝚊𝚕}\_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏}$ (weighted assignment).

implies: $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}$.

application area: assignment.

filtering: cost filtering constraint.

modelling: cost matrix, scalar product.

problems: weighted assignment.

puzzles: magic square, magic hexagon.

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

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

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

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 ${((i-1)·|\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂})|+j)}^{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)