[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.

Figure 5.167.1 gives all solutions to the following non ground instance of the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}\_\mathrm{𝚠𝚒𝚝𝚑}\_\mathrm{𝚌𝚘𝚜𝚝𝚜}$ constraint:

    $V_1\in [3,4]$, $V_2\in [2,3]$, $V_3\in [1,2]$, $V_4\in [2,4]$, $V_5\in [2,3]$, $V_6\in [1,2]$,

$O_1\in [1,1]$, $O_2\in [2,3]$, $O_3\in [0,1]$, $O_4\in [2,3]$,

$C\in [0,16]$,

    $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}\_\mathrm{𝚠𝚒𝚝𝚑}\_\mathrm{𝚌𝚘𝚜𝚝𝚜}$$(\langle V_1,V_2,V_3,V_4,V_5,V_6\rangle$,

                                     $\langle 1O_1,2O_2,3O_3,4O_4\rangle$,

                                     $\langle 115,120,131,141$, 

                                      $212,227,230,242$, 

                                      $313,323,336,346$, 

                                      $414,423,430,440$, 

                                      $512,520,536,543$, 

                                      $615,624,635,644\rangle ,C)$.

Figure 5.167.1. All solutions corresponding to the non ground example of the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}\_\mathrm{𝚠𝚒𝚝𝚑}\_\mathrm{𝚌𝚘𝚜𝚝𝚜}$ constraint of the All solutions slot

• Functional dependency: $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}.\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}$ determined by $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$.

• Functional dependency: $\mathrm{𝙲𝙾𝚂𝚃}$ determined by $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$, $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ and $\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}$.

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 a 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}},\cdots ,{𝚇}_{𝚗})$ and ${\alpha }_1·{𝚇}_{\mathtt{1}}+{\alpha }_2·{𝚇}_{\mathtt{2}}+\cdots +{\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.

A filtering algorithm achieving arc-consistency independently on each side (i.e., the greater than or equal to side and the less than or equal to side) of the $\mathrm{𝚐𝚕𝚘𝚋𝚊𝚕}\_\mathrm{𝚌𝚊𝚛𝚍𝚒𝚗𝚊𝚕𝚒𝚝𝚢}\_\mathrm{𝚠𝚒𝚝𝚑}\_\mathrm{𝚌𝚘𝚜𝚝𝚜}$ constraint is described in [Regin99a], [Regin02]. This algorithm assumes for each value a fixed minimum and maximum number of occurrences. If we rather have occurrence variables, the Reformulation slot explains how to also obtain some propagation from the cost variable back to the occurrence variables.

Let $n$ and $m$ respectively denote the number of items of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ and of the $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}$ collections. Let $v_1,v_2,\cdots ,v_m$ denote the values $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\left[1\right].\mathrm{𝚟𝚊𝚕},\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\left[2\right].\mathrm{𝚟𝚊𝚕},\cdots ,\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\left[m\right].\mathrm{𝚟𝚊𝚕}$. In addition let ${\mathrm{𝐿𝐼𝑁𝐸}}_i$ (with $i\in [1,n]$) denote the values $\langle \mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}[m·(i-1)+1].𝚌,\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}[m·(i-1)+2].𝚌,\cdots ,\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}[m·i].𝚌\rangle$, i.e., line $i$ of the matrix $\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}$.

By introducing $2·n$ auxiliary variables $U_1,U_2,\cdots ,U_n$ and $C_1,C_2,\cdots ,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$ (with $i\in [1,|\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}\left|\right]$) of the $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ collection a first $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(U_i,\langle v_1,v_2,\cdots ,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+\cdots +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$.

We now show how to add implied constraints that can also propagate from the cost variable back to the occurrence variables. Let $O_1,O_2,\cdots ,O_m$ respectively denote the variables $\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\left[1\right].\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎},\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\left[2\right].\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎},\cdots ,\mathrm{𝚅𝙰𝙻𝚄𝙴𝚂}\left[m\right].\mathrm{𝚗𝚘𝚌𝚌𝚞𝚛𝚛𝚎𝚗𝚌𝚎}$. The idea is to get for each value $v_i$ (with $i\in [1,m]$) an idea of its minimum and maximum contribution in the total cost $\mathrm{𝙲𝙾𝚂𝚃}$ that is linked to the number of times it is assigned to a variables of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$. E.g., if value $v_i$ (with $i\in [1,m]$) is used twice, then the corresponding minimum (respectively maximum) contribution in the total cost $\mathrm{𝙲𝙾𝚂𝚃}$ will be at least equal to the sum of the two smallest (respectively largest) costs attached to row $i$. Let $D_i$ (with $i\in [1,m]$) denotes the contribution that stems from the variables of $\mathrm{𝚅𝙰𝚁𝙸𝙰𝙱𝙻𝙴𝚂}$ that are assigned value $v_i$. For each value $v_i$ (with $i\in [1,m]$) we create one $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$ constraint for linking $O_i+1$ to the corresponding minimum contribution ${\mathrm{𝐿𝑂𝑊}}_i$. The table of that $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$ constraint has $n+1$ entries, where entry $j$ (with $j\in [0,n]$) corresponds to the sum of the $j^{\mathrm{𝑡ℎ}}$ smallest entries of row $i$ of the cost matrix $\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}$. Similarly we create for each value $v_i$ (with $i\in [1,m]$) one $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$ constraint for linking $O_i+1$ to the corresponding maximum contribution ${\mathrm{𝑈𝑃}}_i$. The table of that $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$ constraint also has $n+1$ entries, where entry $j$ (with $j\in [0,n]$) corresponds to the sum of the $j^{\mathrm{𝑡ℎ}}$ largest entries of row $i$ of the cost matrix $\mathrm{𝙼𝙰𝚃𝚁𝙸𝚇}$.

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

   $\mathrm{𝙲𝙾𝚂𝚃}=D_1+D_2+D_3$,

   $n=O_1+O_2+O_3$,

   $P_1=O_1+1$,

   $P_2=O_2+1$,

   $P_3=O_3+1$,

   $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(P_1,\langle 0,0,1,4,8\rangle ,{\mathrm{𝐿𝑂𝑊}}_1)$,

   $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(P_2,\langle 0,0,0,1,3\rangle ,{\mathrm{𝐿𝑂𝑊}}_2)$,

   $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(P_3,\langle 0,1,7,14,22\rangle ,{\mathrm{𝐿𝑂𝑊}}_3)$,

   $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(P_1,\langle 0,4,7,8,8\rangle ,{\mathrm{𝑈𝑃}}_1)$,

   $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(P_2,\langle 0,2,3,3,3\rangle ,{\mathrm{𝑈𝑃}}_2)$,

   $\mathrm{𝚎𝚕𝚎𝚖𝚎𝚗𝚝}$$(P_3,\langle 0,8,15,21,22\rangle ,{\mathrm{𝑈𝑃}}_3)$,

   ${\mathrm{𝐿𝑂𝑊}}_1\le D_1$, $D_1\le {\mathrm{𝑈𝑃}}_1$,

   ${\mathrm{𝐿𝑂𝑊}}_2\le D_2$, $D_2\le {\mathrm{𝑈𝑃}}_2$,

   ${\mathrm{𝐿𝑂𝑊}}_3\le D_3$, $D_3\le {\mathrm{𝑈𝑃}}_3$.

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.

constraint arguments: pure functional dependency.

filtering: cost filtering constraint.

heuristics: regret based heuristics, regret based heuristics in matrix problems.

modelling: cost matrix, scalar product, functional dependency.

problems: weighted assignment.

puzzles: magic square, magic hexagon.

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