### 3.7.18. Assignment to the same set of values

modelling: assignment to the same set of values Given several mutually disjoint finite sets of values ${\mathrm{๐ฎ}}_{1},{\mathrm{๐ฎ}}_{2},โฏ,{\mathrm{๐ฎ}}_{m}$ $\left(m>1\right)$ such that ${S}_{1}โช{S}_{2}โชโฏโช{S}_{m}=\left\{1,2,โฏ,p\right\}$, as well as a set of variables ${V}_{1},{V}_{2},โฏ,{V}_{n}$, the assignment to the same set of values subproblem consists of assigning all variables ${V}_{1},{V}_{2},โฏ,{V}_{n}$ values that belong to the same set ${\mathrm{๐ฎ}}_{i}$ $\left(1โคiโคm\right)$. As we will see later on, this subproblem arises naturally in many resource assignment problems where an additional constraint between variables ${V}_{1},{V}_{2},โฏ,{V}_{n}$ also has to hold. The subproblem can be modelled as a conjunction of $\mathrm{๐๐๐๐๐๐๐}$ constraints of the form:

ย ย ย $โฏ$

where if and only if $iโ{\mathrm{๐ฎ}}_{j}$ (i.e., corresponds to the index of the set that contains value $i$). The $k$-th $\mathrm{๐๐๐๐๐๐๐}$ constraint expresses that variable ${V}_{k}$ is assigned a value in set ${\mathrm{๐ฎ}}_{\mathrm{๐๐ธ๐}}_\mathrm{๐ผ๐๐ท๐ธ๐}$. Since all $\mathrm{๐๐๐๐๐๐๐}$ constraints share the same third argument this forces all variables ${V}_{1},{V}_{2},โฏ,{V}_{n}$ to be assigned a value within the same set. Note that this conjunction of $\mathrm{๐๐๐๐๐๐๐}$ constraints corresponds to a Berge-acyclic constraint network. Consequently, one can achieve arc-consistency on this subproblem provided that arc-consistency is enforced on each $\mathrm{๐๐๐๐๐๐๐}$ constraint.

As an example, consider the four sets of values ${\mathrm{๐ฎ}}_{1}=\left\{3,4,8\right\}$, ${\mathrm{๐ฎ}}_{2}=\left\{1,5\right\}$, ${\mathrm{๐ฎ}}_{3}=\left\{6,7\right\}$, and ${\mathrm{๐ฎ}}_{4}=\left\{2,9\right\}$, as well as four variables $w$, $x$, $y$ and $z$ that all must be assigned values that belong to the same set ${\mathrm{๐ฎ}}_{s}$ $\left(1โคsโค4\right)$. This leads to the following conjunction of $\mathrm{๐๐๐๐๐๐๐}$ constraints:

ย ย ย $\mathrm{๐๐๐๐๐๐๐}$$\left(w,โฉ2,4,1,1,2,3,3,1,4โช,s\right)โง$

ย ย ย $\mathrm{๐๐๐๐๐๐๐}$$\left(x,โฉ2,4,1,1,2,3,3,1,4โช,s\right)โง$

ย ย ย $\mathrm{๐๐๐๐๐๐๐}$$\left(y,โฉ2,4,1,1,2,3,3,1,4โช,s\right)โง$

ย ย ย $\mathrm{๐๐๐๐๐๐๐}$$\left(z,โฉ2,4,1,1,2,3,3,1,4โช,s\right)$.

The first entry of the table $โฉ2,4,1,1,2,3,3,1,4โช$ is set to 2 since value 1 belongs to ${\mathrm{๐ฎ}}_{2}$. Similarly, the second entry of the table is set of 4 since value 2 belongs to ${\mathrm{๐ฎ}}_{4}$. The same logic is used for building up the other entries of the table.

A generalisation of this subproblem consists in lifting the restriction that the sets of values ${\mathrm{๐ฎ}}_{1},{\mathrm{๐ฎ}}_{2},โฏ,{\mathrm{๐ฎ}}_{m}$ are mutually disjoint. The only change to adapt the previous model is to replace within each $\mathrm{๐๐๐๐๐๐๐}$ constraint each value ${\mathrm{๐ฃ๐๐}}_{i}$ $\left(1โคiโคp\right)$ by a value variable ${\mathrm{๐๐๐}}_{i}$ (i.e., each value of a value variable represents a set containing $i$), where $jโ\mathrm{๐๐๐}\left({\mathrm{๐๐๐}}_{i}\right)$ if and only if $iโ{\mathrm{๐ฎ}}_{j}$. Distinct $\mathrm{๐๐๐๐๐๐๐}$ constraints will get distinct value variables. As an example, consider the previous four sets of values where we add value 2 to ${\mathrm{๐ฎ}}_{1}$ and value 5 to ${\mathrm{๐ฎ}}_{3}$. We now have the sets ${\mathrm{๐ฎ}}_{1}=\left\{2,3,4,8\right\}$, ${\mathrm{๐ฎ}}_{2}=\left\{1,5\right\}$, ${\mathrm{๐ฎ}}_{3}=\left\{5,6,7\right\}$, and ${\mathrm{๐ฎ}}_{4}=\left\{2,9\right\}$ where value 2 occurs both in ${\mathrm{๐ฎ}}_{1}$ and ${\mathrm{๐ฎ}}_{4}$, and value 5 appears both in ${\mathrm{๐ฎ}}_{2}$ and ${\mathrm{๐ฎ}}_{3}$. This leads to the following conjunction of constraints:

ย ย ย $\mathrm{๐๐}$$\left({a}_{1},โฉ1,4โช\right)โง$$\mathrm{๐๐}$$\left({b}_{1},โฉ2,3โช\right)โง$$\mathrm{๐๐๐๐๐๐๐}$$\left(w,โฉ2,{a}_{1},1,1,{b}_{1},3,3,1,4โช,s\right)โง$

ย ย ย $\mathrm{๐๐}$$\left({a}_{2},โฉ1,4โช\right)โง$$\mathrm{๐๐}$$\left({b}_{2},โฉ2,3โช\right)โง$$\mathrm{๐๐๐๐๐๐๐}$$\left(x,โฉ2,{a}_{2},1,1,{b}_{2},3,3,1,4โช,s\right)โง$

ย ย ย $\mathrm{๐๐}$$\left({a}_{3},โฉ1,4โช\right)โง$$\mathrm{๐๐}$$\left({b}_{3},โฉ2,3โช\right)โง$$\mathrm{๐๐๐๐๐๐๐}$$\left(y,โฉ2,{a}_{3},1,1,{b}_{3},3,3,1,4โช,s\right)โง$

ย ย ย $\mathrm{๐๐}$$\left({a}_{4},โฉ1,4โช\right)โง$$\mathrm{๐๐}$$\left({b}_{4},โฉ2,3โช\right)โง$$\mathrm{๐๐๐๐๐๐๐}$$\left(z,โฉ2,{a}_{4},1,1,{b}_{4},3,3,1,4โช,s\right)$.

The domain of the variables ${a}_{i}$ $\left(1โคiโค4\right)$ associated with the second entry of the tableThe table corresponds to the second argument of the $\mathrm{๐๐๐๐๐๐๐}$ constraint. of the $\mathrm{๐๐๐๐๐๐๐}$ constraints is set to 1 and 4 since value 2 belongs to ${\mathrm{๐ฎ}}_{1}$ and to ${\mathrm{๐ฎ}}_{4}$. Similarly, the domain of variables ${b}_{i}$ $\left(1โคiโค4\right)$ associated with the fifth entry is set to 2 and 3 since value 5 belongs to ${\mathrm{๐ฎ}}_{2}$ and ${\mathrm{๐ฎ}}_{3}$. Note that, since variables ${a}_{1}$, ${a}_{2}$, ${a}_{3}$, ${a}_{4}$, ${b}_{1}$, ${b}_{2}$, ${b}_{3}$, ${b}_{4}$ are distinct, the corresponding constraint network is still Berge-acyclic. We now provide an alternative model where the ${i}^{th}$ entry of the table of the ${k}^{th}$ $\left(1โคkโคn\right)$ $\mathrm{๐๐๐๐๐๐๐}$ constraint corresponds to a variable ${S}_{ki}$ for which the initial domain is the set of values that belong to ${\mathrm{๐ฎ}}_{i}$ $\left(1โคiโคm\right)$. We have a conjunction of $\mathrm{๐๐๐๐๐๐๐}$ constraints of the form:

ย ย ย $\mathrm{๐๐๐๐๐๐๐}$$\left(\mathrm{๐๐ธ๐}_\mathrm{๐ผ๐๐ท๐ธ๐},โฉ{S}_{11},{S}_{12},โฏ,{S}_{1m}โช,{V}_{1}\right)โง$

ย ย ย $\mathrm{๐๐๐๐๐๐๐}$$\left(\mathrm{๐๐ธ๐}_\mathrm{๐ผ๐๐ท๐ธ๐},โฉ{S}_{21},{S}_{22},โฏ,{S}_{2m}โช,{V}_{2}\right)โง$

ย ย ย $โฏ$

ย ย ย $\mathrm{๐๐๐๐๐๐๐}$$\left(\mathrm{๐๐ธ๐}_\mathrm{๐ผ๐๐ท๐ธ๐},โฉ{S}_{n1},{S}_{n2},โฏ,{S}_{nm}โช,{V}_{n}\right)$,

where $\mathrm{๐๐ธ๐}_\mathrm{๐ผ๐๐ท๐ธ๐}$ is a variable ranging from 1 to $m$ designating the selected set. This model perhaps seems more natural. However unlike the first model, when the sets ${\mathrm{๐ฎ}}_{1},{\mathrm{๐ฎ}}_{2},โฏ,{\mathrm{๐ฎ}}_{m}$ are mutually disjoint, it enforces using variables instead of integers in the table of each $\mathrm{๐๐๐๐๐๐๐}$ constraint. Like the first model, it is Berge-acyclic.

Now that we have presented two dual models for the assignment to the same set of values subproblem, we introduce the resource assignment with groups pattern, which uses several instances of the subproblem. We consider a set of tasks ${t}_{1},{t}_{2},โฏ,{t}_{q}$ $\left(qโฅ1\right)$ tasks, where each task ${t}_{i}$ $\left(1โคiโคq\right)$ is decomposed into ${s}_{i}$ subtasks ${t}_{ij}$ $\left(1โคjโค{s}_{i}\right)$. All subtasks that belong to one and the same task should be assigned the same group, where groups are defined by the finite sets of values ${\mathrm{๐ฎ}}_{1},{\mathrm{๐ฎ}}_{2},โฏ,{\mathrm{๐ฎ}}_{m}$ $\left(m>1\right)$ introduced early on. For this purpose an assignment variable and a group variable are respectively associated with each subtask and each task. In addition, we also have a resource constraint involving all subtasks. This resource constraint has an assignment dimension corresponding to the different resources where subtasks can potentially be assigned. To each resource corresponds a value of ${S}_{1}โช{S}_{2}โชโฏโช{S}_{m}=\left\{1,2,โฏ,p\right\}$. Depending on the kind of resource constraint we have (e.g.,ย $\mathrm{๐๐๐}_\mathrm{๐๐๐๐๐๐๐}$, $\mathrm{๐๐๐๐๐๐๐๐๐๐๐}$, $\mathrm{๐๐๐๐๐}$, $\mathrm{๐๐๐๐๐}$), each subtask has additional attributes that characterise it. For instance, if we have a $\mathrm{๐๐๐}_\mathrm{๐๐๐๐๐๐๐}$ constraint then, in addition to the assignment dimension that corresponds to the bin where a subtask will be assigned, we also have a weight attribute that describes how much space a subtask uses in a bin. Then the $\mathrm{๐๐๐}_\mathrm{๐๐๐๐๐๐๐}$ constraint expresses that the total weight of the subtasks in each bin does not exceed a given fixed capacity.

Figureย 3.7.3 illustrates the constraint network associated with the resource assignment with groups pattern. Lower circles represent the group variables associated with the different tasks (three tasks in the example), while all the other circles represent the attributes of the different subtasks (i.e., vertically aligned circles correspond to the attributes of a given subtask). All circles that are associated with the same task are coloured with the same colour. As said before, each subtask has an attribute that gives the resource to which the resource will be assigned (called assignment variables in Figureย 3.7.3) and other attributes that depend of the resource constraint we are considering (called other subtask attributes in the Figure). Each blue rounded box corresponds to a group constraint which enforces all subtasks of a given task to be assigned the same group (i.e., within this blue box, each line segment represents an $\mathrm{๐๐๐๐๐๐๐}$ constraint of the assignment to the same set of values subproblem). Finally, the pink rounded box represents the resource constraint that involves all subtasks.

Before illustrating the resource assignment with groups pattern on a particular resource constraint, we first point out a potential weakness that is inherent to this constraint network, no matter what kind of resource constraint we use. When pruning the assignment variables, the resource constraint will ignore the groups (since the resource constraint is not aware of the $\mathrm{๐๐๐๐๐๐๐}$ constraints) and will therefore miss some filtering. Consequently one may complete the constraint network by some global necessary conditions. When fixing variables it may be a good idea to fix all variables that are attached to one task before considering the next task. While fixing the variables of a task one may first assign its group variable, and second fix the variables of its subtasks; again we may prefer to fix all variables of a subtask before considering the next subtask. The idea behind this heuristics is to try to avoid the creation of infeasible subproblems during search.

Figureย 3.7.4 illustrates the resource assignment with groups pattern when the resource constraint corresponds to a $\mathrm{๐๐๐}_\mathrm{๐๐๐๐๐๐๐}$ constraint. As in Figureย 3.7.3, we have three tasks ${t}_{1}$, ${t}_{2}$ and ${t}_{3}$ such that:

• Three subtasks ${t}_{11}$, ${t}_{12}$ and ${t}_{13}$ are associated with task ${t}_{1}$. They have a respective weight of 2, 3 and 2 and are coloured in green in Figureย 3.7.4.

• Two subtasks ${t}_{21}$ and ${t}_{22}$ of respective weight 2 and 3 are associated with task ${t}_{2}$. They are coloured in yellow.

• Two subtasks ${t}_{31}$ and ${t}_{32}$ of respective weight 2 and 1 are associated with task ${t}_{3}$. They are coloured in orange.

We consider 9 bins that are partitioned into four groups of bins ${\mathrm{๐ฎ}}_{1}=\left\{3,4,8\right\}$ (coloured in light blue in Figureย 3.7.4), ${\mathrm{๐ฎ}}_{2}=\left\{1,5\right\}$ (coloured in light green), ${\mathrm{๐ฎ}}_{3}=\left\{6,7\right\}$ (coloured in light brown), and ${\mathrm{๐ฎ}}_{4}=\left\{2,9\right\}$ (coloured in light violet), and enforce that all subtasks that are associated with the same task are assigned the same group of bins. In addition, the sum of the weights of the subtasks that are assigned the same bin should not exceed the capacity of the bins, 5 in our example. Within the solution depicted by Figureย 3.7.4, all constraints are satisfied since:

1. For each task, all its subtasks are assigned the same group of bins (i.e., all subtasks that have the same colour are assigned bins with the same colour).

2. The capacity constraint of each bin is respected (i.e., the overall capacity of five is never exceeded).

The conjunction of constraints corresponding to this solution is:

ย ย ย $\mathrm{๐๐๐๐๐๐๐}$$\left(4,โฉ2,4,1,1,2,3,3,1,4โช,1\right)โง$

ย ย ย $\mathrm{๐๐๐๐๐๐๐}$$\left(8,โฉ2,4,1,1,2,3,3,1,4โช,1\right)โง$

ย ย ย $\mathrm{๐๐๐๐๐๐๐}$$\left(4,โฉ2,4,1,1,2,3,3,1,4โช,1\right)โง$

ย ย ย $\mathrm{๐๐๐๐๐๐๐}$$\left(2,โฉ2,4,1,1,2,3,3,1,4โช,4\right)โง$

ย ย ย $\mathrm{๐๐๐๐๐๐๐}$$\left(9,โฉ2,4,1,1,2,3,3,1,4โช,4\right)โง$

ย ย ย $\mathrm{๐๐๐๐๐๐๐}$$\left(2,โฉ2,4,1,1,2,3,3,1,4โช,4\right)โง$

ย ย ย $\mathrm{๐๐๐๐๐๐๐}$$\left(9,โฉ2,4,1,1,2,3,3,1,4โช,4\right)โง$

ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย

ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย .

For each subtask we have one $\mathrm{๐๐๐๐๐๐๐}$ constraint expressing that all subtasks of a given task are assigned the same group of bins. Finally we have one $\mathrm{๐๐๐}_\mathrm{๐๐๐๐๐๐๐}$ constraint expressing the capacity condition.

We now quote two concrete examples of the resource assignment with groups pattern:

• Given, (1)ย a set of jobs where each job is decomposed into a set of tasks, each of them requiring an amount of memory for its execution, as well as (2)ย a set of potential machines, each of them having a given available memory, organised into clusters, the problem is to:

• Assign all tasks to machines in such a way that tasks from the same job are assigned the same cluster.

• Fulfil the available memory constraint of each machine (i.e., the sum of the required memory of all tasks that are assigned a given machine does not exceed the machine available memory).

This concrete problem corresponds to the example presented in Figureย 3.7.4.

• Given, (1)ย a set of maintenance activities where each maintenance activity is decomposed into a set of subactivities, each of them requiring a specific skill and a given duration, as well as (2)ย a set of technicians, each of them having its own home base location and its own working time window, the problem is to:

• Assign all maintenance subactivities to technicians in such a way that subactivities from the same activity are assigned technicians that have the same home base location (i.e., each subactivity should be assigned a single technician).

• Fulfil both the working time window of each technician, and the fact that subactivities that are assigned the same technician should not overlap (i.e., subactivities must be assigned a starting time and preemption is not allowed).

In this problem we replace the $\mathrm{๐๐๐}_\mathrm{๐๐๐๐๐๐๐}$ constraint by a $\mathrm{๐๐๐๐๐๐๐๐๐๐๐}$$\left(\mathrm{๐๐ฐ๐๐บ๐},\mathrm{๐ผ๐ฐ๐ฒ๐ท๐ธ๐ฝ๐ด๐},โค\right)$ constraint. To each item of the $\mathrm{๐๐ฐ๐๐บ๐}$ collection corresponds a subactivity, such that:

• Its $\mathrm{๐๐๐๐๐๐๐}$ attribute designates the potential technicians that can take care of this subactivity.

• Its $\mathrm{๐๐๐๐๐๐}$ attribute corresponds to the timepoint where the subactivity will actually start.

• Its $\mathrm{๐๐๐๐๐๐๐๐}$ attribute is set to the duration of the corresponding subactivity.

• Its $\mathrm{๐๐๐}$ attribute is equal to $\mathrm{๐๐๐๐๐๐}+\mathrm{๐๐๐๐๐๐๐๐}$.

• Its $\mathrm{๐๐๐๐๐๐}$ attribute is set to one.

In addition to the subactivities, we also introduce for each technician two fixed dummy tasks for preventing assigning subactivities outside its time window. To each item of the $\mathrm{๐ผ๐ฐ๐ฒ๐ท๐ธ๐ฝ๐ด๐}$ collection corresponds a technician, such that:

• Its $\mathrm{๐๐}$ attribute is a fixed integer that uniquely identifies the technician.

• Its $\mathrm{๐๐๐๐๐๐๐๐ข}$ attribute is set to one since it cannot perform more than one subactivity at any timepoint.