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 ๐’ฎ 1 ,๐’ฎ 2 ,โ‹ฏ,๐’ฎ m (m>1) such that S 1 โˆชS 2 โˆชโ‹ฏโˆชS m ={1,2,โ‹ฏ,p}, 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 ๐’ฎ i (1โ‰คiโ‰คm). 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 ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š constraints of the form:

ย ย ย ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š(V 1 ,โŒฉ๐‘ ๐‘’๐‘ก_๐‘œ๐‘“_๐‘ฃ๐‘Ž๐‘™ 1 ,๐‘ ๐‘’๐‘ก_๐‘œ๐‘“_๐‘ฃ๐‘Ž๐‘™ 2 ,โ‹ฏ,๐‘ ๐‘’๐‘ก_๐‘œ๐‘“_๐‘ฃ๐‘Ž๐‘™ p โŒช,๐‘†๐ธ๐‘‡_๐ผ๐‘๐ท๐ธ๐‘‹) โˆง

ย ย ย ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š(V 2 ,โŒฉ๐‘ ๐‘’๐‘ก_๐‘œ๐‘“_๐‘ฃ๐‘Ž๐‘™ 1 ,๐‘ ๐‘’๐‘ก_๐‘œ๐‘“_๐‘ฃ๐‘Ž๐‘™ 2 ,โ‹ฏ,๐‘ ๐‘’๐‘ก_๐‘œ๐‘“_๐‘ฃ๐‘Ž๐‘™ p โŒช,๐‘†๐ธ๐‘‡_๐ผ๐‘๐ท๐ธ๐‘‹) โˆง

ย ย ย โ‹ฏ

ย ย ย ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š(V n ,โŒฉ๐‘ ๐‘’๐‘ก_๐‘œ๐‘“_๐‘ฃ๐‘Ž๐‘™ 1 ,๐‘ ๐‘’๐‘ก_๐‘œ๐‘“_๐‘ฃ๐‘Ž๐‘™ 2 ,โ‹ฏ,๐‘ ๐‘’๐‘ก_๐‘œ๐‘“_๐‘ฃ๐‘Ž๐‘™ p โŒช,๐‘†๐ธ๐‘‡_๐ผ๐‘๐ท๐ธ๐‘‹),

where ๐‘ ๐‘’๐‘ก_๐‘œ๐‘“_๐‘ฃ๐‘Ž๐‘™ i =j if and only if iโˆˆ๐’ฎ j (i.e., ๐‘ ๐‘’๐‘ก_๐‘œ๐‘“_๐‘ฃ๐‘Ž๐‘™ i corresponds to the index of the set that contains value i). The k-th ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š constraint expresses that variable V k is assigned a value in set ๐’ฎ ๐‘†๐ธ๐‘‡ _๐ผ๐‘๐ท๐ธ๐‘‹. Since all ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š 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 ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š 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 ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š constraint.

As an example, consider the four sets of values ๐’ฎ 1 ={3,4,8}, ๐’ฎ 2 ={1,5}, ๐’ฎ 3 ={6,7}, and ๐’ฎ 4 ={2,9}, as well as four variables w, x, y and z that all must be assigned values that belong to the same set ๐’ฎ s (1โ‰คsโ‰ค4). This leads to the following conjunction of ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š constraints:

ย ย ย ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š(w,โŒฉ2,4,1,1,2,3,3,1,4โŒช,s) โˆง

ย ย ย ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š(x,โŒฉ2,4,1,1,2,3,3,1,4โŒช,s) โˆง

ย ย ย ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š(y,โŒฉ2,4,1,1,2,3,3,1,4โŒช,s) โˆง

ย ย ย ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š(z,โŒฉ2,4,1,1,2,3,3,1,4โŒช,s).

The first entry of the table โŒฉ2,4,1,1,2,3,3,1,4โŒช is set to 2 since value 1 belongs to ๐’ฎ 2 . Similarly, the second entry of the table is set of 4 since value 2 belongs to ๐’ฎ 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 ๐’ฎ 1 ,๐’ฎ 2 ,โ‹ฏ,๐’ฎ m are mutually disjoint. The only change to adapt the previous model is to replace within each ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š constraint each value ๐‘ฃ๐‘Ž๐‘™ i (1โ‰คiโ‰คp) by a value variable ๐‘‰๐‘Ž๐‘™ i (i.e., each value of a value variable represents a set containing i), where jโˆˆ๐‘‘๐‘œ๐‘š(๐‘‰๐‘Ž๐‘™ i ) if and only if iโˆˆ๐’ฎ j . Distinct ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š constraints will get distinct value variables. As an example, consider the previous four sets of values where we add value 2 to ๐’ฎ 1 and value 5 to ๐’ฎ 3 . We now have the sets ๐’ฎ 1 ={2,3,4,8}, ๐’ฎ 2 ={1,5}, ๐’ฎ 3 ={5,6,7}, and ๐’ฎ 4 ={2,9} where value 2 occurs both in ๐’ฎ 1 and ๐’ฎ 4 , and value 5 appears both in ๐’ฎ 2 and ๐’ฎ 3 . This leads to the following conjunction of constraints:

ย ย ย ๐š’๐š—(a 1 ,โŒฉ1,4โŒช) โˆง ๐š’๐š—(b 1 ,โŒฉ2,3โŒช) โˆง ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š(w,โŒฉ2,a 1 ,1,1,b 1 ,3,3,1,4โŒช,s) โˆง

ย ย ย ๐š’๐š—(a 2 ,โŒฉ1,4โŒช) โˆง ๐š’๐š—(b 2 ,โŒฉ2,3โŒช) โˆง ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š(x,โŒฉ2,a 2 ,1,1,b 2 ,3,3,1,4โŒช,s) โˆง

ย ย ย ๐š’๐š—(a 3 ,โŒฉ1,4โŒช) โˆง ๐š’๐š—(b 3 ,โŒฉ2,3โŒช) โˆง ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š(y,โŒฉ2,a 3 ,1,1,b 3 ,3,3,1,4โŒช,s) โˆง

ย ย ย ๐š’๐š—(a 4 ,โŒฉ1,4โŒช) โˆง ๐š’๐š—(b 4 ,โŒฉ2,3โŒช) โˆง ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š(z,โŒฉ2,a 4 ,1,1,b 4 ,3,3,1,4โŒช,s).

The domain of the variables a i (1โ‰คiโ‰ค4) associated with the second entry of the tableThe table corresponds to the second argument of the ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š constraint. of the ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š constraints is set to 1 and 4 since value 2 belongs to ๐’ฎ 1 and to ๐’ฎ 4 . Similarly, the domain of variables b i (1โ‰คiโ‰ค4) associated with the fifth entry is set to 2 and 3 since value 5 belongs to ๐’ฎ 2 and ๐’ฎ 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 (1โ‰คkโ‰คn) ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š constraint corresponds to a variable S ki for which the initial domain is the set of values that belong to ๐’ฎ i (1โ‰คiโ‰คm). We have a conjunction of ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š constraints of the form:

ย ย ย ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š(๐‘†๐ธ๐‘‡_๐ผ๐‘๐ท๐ธ๐‘‹,โŒฉS 11 ,S 12 ,โ‹ฏ,S 1m โŒช,V 1 ) โˆง

ย ย ย ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š(๐‘†๐ธ๐‘‡_๐ผ๐‘๐ท๐ธ๐‘‹,โŒฉS 21 ,S 22 ,โ‹ฏ,S 2m โŒช,V 2 ) โˆง

ย ย ย โ‹ฏ

ย ย ย ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š(๐‘†๐ธ๐‘‡_๐ผ๐‘๐ท๐ธ๐‘‹,โŒฉS n1 ,S n2 ,โ‹ฏ,S nm โŒช,V n ),

where ๐‘†๐ธ๐‘‡_๐ผ๐‘๐ท๐ธ๐‘‹ 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 ๐’ฎ 1 ,๐’ฎ 2 ,โ‹ฏ,๐’ฎ m are mutually disjoint, it enforces using variables instead of integers in the table of each ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š 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 (qโ‰ฅ1) tasks, where each task t i (1โ‰คiโ‰คq) is decomposed into s i subtasks t ij (1โ‰คjโ‰คs i ). 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 ๐’ฎ 1 ,๐’ฎ 2 ,โ‹ฏ,๐’ฎ m (m>1) 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 ={1,2,โ‹ฏ,p}. Depending on the kind of resource constraint we have (e.g.,ย ๐š‹๐š’๐š—_๐š™๐šŠ๐šŒ๐š”๐š’๐š—๐š, ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ๐šœ, ๐š๐š’๐š๐š๐š—, ๐š๐šŽ๐š˜๐šœ๐š), each subtask has additional attributes that characterise it. For instance, if we have a ๐š‹๐š’๐š—_๐š™๐šŠ๐šŒ๐š”๐š’๐š—๐š 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 ๐š‹๐š’๐š—_๐š™๐šŠ๐šŒ๐š”๐š’๐š—๐š constraint expresses that the total weight of the subtasks in each bin does not exceed a given fixed capacity.

Figure 3.7.3. Illustration of the constraint network associated with the resource assignment with groups pattern
ctrs/preface-143-tikz

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 ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š 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 ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š 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. Illustration of the resource assignment with groups pattern in the context of a ๐š‹๐š’๐š—_๐š™๐šŠ๐šŒ๐š”๐š’๐š—๐š resource constraint (subtasks of the same colour are assigned to the same group of bins)
ctrs/preface-144-tikz

Figureย 3.7.4 illustrates the resource assignment with groups pattern when the resource constraint corresponds to a ๐š‹๐š’๐š—_๐š™๐šŠ๐šŒ๐š”๐š’๐š—๐š 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 ๐’ฎ 1 ={3,4,8} (coloured in light blue in Figureย 3.7.4), ๐’ฎ 2 ={1,5} (coloured in light green), ๐’ฎ 3 ={6,7} (coloured in light brown), and ๐’ฎ 4 ={2,9} (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:

ย ย ย ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š(4,โŒฉ2,4,1,1,2,3,3,1,4โŒช,1) โˆง

ย ย ย ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š(8,โŒฉ2,4,1,1,2,3,3,1,4โŒช,1) โˆง

ย ย ย ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š(4,โŒฉ2,4,1,1,2,3,3,1,4โŒช,1) โˆง

ย ย ย ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š(2,โŒฉ2,4,1,1,2,3,3,1,4โŒช,4) โˆง

ย ย ย ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š(9,โŒฉ2,4,1,1,2,3,3,1,4โŒช,4) โˆง

ย ย ย ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š(2,โŒฉ2,4,1,1,2,3,3,1,4โŒช,4) โˆง

ย ย ย ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š(9,โŒฉ2,4,1,1,2,3,3,1,4โŒช,4) โˆง

ย ย ย ๐š‹๐š’๐š—_๐š™๐šŠ๐šŒ๐š”๐š’๐š—๐š(5,โŒฉ๐š‹๐š’๐š—-4 ๐š ๐šŽ๐š’๐š๐š‘๐š-2, ๐š‹๐š’๐š—-8 ๐š ๐šŽ๐š’๐š๐š‘๐š-3, ๐š‹๐š’๐š—-4 ๐š ๐šŽ๐š’๐š๐š‘๐š-2,

ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ๐š‹๐š’๐š—-2 ๐š ๐šŽ๐š’๐š๐š‘๐š-2, ๐š‹๐š’๐š—-9 ๐š ๐šŽ๐š’๐š๐š‘๐š-3,

ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ย ๐š‹๐š’๐š—-2 ๐š ๐šŽ๐š’๐š๐š‘๐š-2, ๐š‹๐š’๐š—-9 ๐š ๐šŽ๐š’๐š๐š‘๐š-1โŒช).

For each subtask we have one ๐šŽ๐š•๐šŽ๐š–๐šŽ๐š—๐š constraint expressing that all subtasks of a given task are assigned the same group of bins. Finally we have one ๐š‹๐š’๐š—_๐š™๐šŠ๐šŒ๐š”๐š’๐š—๐š 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 ๐š‹๐š’๐š—_๐š™๐šŠ๐šŒ๐š”๐š’๐š—๐š constraint by a ๐šŒ๐šž๐š–๐šž๐š•๐šŠ๐š๐š’๐šŸ๐šŽ๐šœ(๐šƒ๐™ฐ๐š‚๐™บ๐š‚,๐™ผ๐™ฐ๐™ฒ๐™ท๐™ธ๐™ฝ๐™ด๐š‚,โ‰ค) constraint. To each item of the ๐šƒ๐™ฐ๐š‚๐™บ๐š‚ collection corresponds a subactivity, such that:

    • Its ๐š–๐šŠ๐šŒ๐š‘๐š’๐š—๐šŽ attribute designates the potential technicians that can take care of this subactivity.

    • Its ๐š˜๐š›๐š’๐š๐š’๐š— attribute corresponds to the timepoint where the subactivity will actually start.

    • Its ๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š— attribute is set to the duration of the corresponding subactivity.

    • Its ๐šŽ๐š—๐š attribute is equal to ๐š˜๐š›๐š’๐š๐š’๐š—+๐š๐šž๐š›๐šŠ๐š๐š’๐š˜๐š—.

    • Its ๐š‘๐šŽ๐š’๐š๐š‘๐š 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 ๐™ผ๐™ฐ๐™ฒ๐™ท๐™ธ๐™ฝ๐™ด๐š‚ collection corresponds a technician, such that:

    • Its ๐š’๐š attribute is a fixed integer that uniquely identifies the technician.

    • Its ๐šŒ๐šŠ๐š™๐šŠ๐šŒ๐š’๐š๐šข attribute is set to one since it cannot perform more than one subactivity at any timepoint.