### 3.7.17. Assignment dimension

A constraint for handlingΒ placement problems involving orthotopes, where one of the dimensions of the placement space is so called an assignment dimension (i.e., one of the attributes of a collection passed as argument indicates the assignment dimension β the attribute is shown in parenthesis for each constraint). In order to illustrate the notion of assignment dimension let us first introduce three typical examples described in FigureΒ 3.7.2:

• PartΒ (A) of FigureΒ 3.7.2 considers aΒ scheduling problem where we have both to assign a task to a machine and to fix its start to a time-point, in such a way that two tasks that overlap in time are not assigned to the same machine. In this context the different potential machines where tasks can be assigned is called an assignment dimension. This problem can be directly modelled by a $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$, a $\mathrm{\pi \pi \pi \pi \pi }$ or a $\mathrm{\pi \pi \pi \pi \pi }$ constraint. The corresponding three ground instances encoding the example are (attributes related to the assignment dimension are shown in bold):

• $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$$\left($

Β Β Β $\beta ©\mathrm{\pi \pi \pi \pi \pi \pi \pi }-\mathbf{1}\mathrm{\pi \pi \pi \pi \pi \pi }-2\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }-2\mathrm{\pi \pi \pi }-4\mathrm{\pi \pi \pi \pi \pi \pi }-1,$

Β Β Β Β $\mathrm{\pi \pi \pi \pi \pi \pi \pi }-\mathbf{3}\mathrm{\pi \pi \pi \pi \pi \pi }-4\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }-3\mathrm{\pi \pi \pi }-7\mathrm{\pi \pi \pi \pi \pi \pi }-1,$

Β Β Β Β $\mathrm{\pi \pi \pi \pi \pi \pi \pi }-\mathbf{1}\mathrm{\pi \pi \pi \pi \pi \pi }-7\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }-1\mathrm{\pi \pi \pi }-8\mathrm{\pi \pi \pi \pi \pi \pi }-1\beta ͺ,$

Β Β Β $\beta ©\mathrm{\pi \pi }-\mathbf{1}\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi ’}-\mathbf{1},$

Β Β Β Β $\mathrm{\pi \pi }-\mathbf{2}\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi ’}-\mathbf{1},$

Β Β Β Β $\mathrm{\pi \pi }-\mathbf{3}\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi ’}-\mathbf{1}\beta ͺ\right)$

• $\mathrm{\pi \pi \pi \pi \pi }$$\left($

Β Β Β $\beta ©\mathrm{\pi \pi \pi \pi }-\beta ©\mathrm{\pi \pi \pi }-2\mathrm{\pi \pi \pi £}-2\mathrm{\pi \pi \pi }-4,\mathrm{\pi \pi \pi }-\mathbf{1}\mathrm{\pi \pi \pi £}-\mathbf{1}\mathrm{\pi \pi \pi }-\mathbf{2}\beta ͺ,$

Β Β Β Β $\mathrm{\pi \pi \pi \pi }-\beta ©\mathrm{\pi \pi \pi }-4\mathrm{\pi \pi \pi £}-3\mathrm{\pi \pi \pi }-7,\mathrm{\pi \pi \pi }-\mathbf{3}\mathrm{\pi \pi \pi £}-\mathbf{1}\mathrm{\pi \pi \pi }-\mathbf{4}\beta ͺ,$

Β Β Β Β $\mathrm{\pi \pi \pi \pi }-\beta ©\mathrm{\pi \pi \pi }-7\mathrm{\pi \pi \pi £}-1\mathrm{\pi \pi \pi }-8,\mathrm{\pi \pi \pi }-\mathbf{1}\mathrm{\pi \pi \pi £}-\mathbf{1}\mathrm{\pi \pi \pi }-\mathbf{2}\beta ͺ\beta ͺ\right)$

• $\mathrm{\pi \pi \pi \pi \pi }$$\left(2,\beta ©\mathrm{\pi \pi \pi }-1\mathrm{\pi \pi \pi }-1\mathrm{\pi ‘}-\beta ©2,\mathbf{1}\beta ͺ,$

Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-2\mathrm{\pi \pi \pi }-2\mathrm{\pi ‘}-\beta ©4,\mathbf{3}\beta ͺ,$

Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-3\mathrm{\pi \pi \pi }-3\mathrm{\pi ‘}-\beta ©7,\mathbf{1}\beta ͺ\beta ͺ$

Β Β Β Β Β Β Β Β Β Β $\beta ©\mathrm{\pi \pi \pi }-1\mathrm{\pi }-\beta ©0,\mathbf{0}\beta ͺ\mathrm{\pi }-\beta ©2,\mathbf{1}\beta ͺ,$

Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-2\mathrm{\pi }-\beta ©0,\mathbf{0}\beta ͺ\mathrm{\pi }-\beta ©3,\mathbf{1}\beta ͺ,$

Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-3\mathrm{\pi }-\beta ©0,\mathbf{0}\beta ͺ\mathrm{\pi }-\beta ©1,\mathbf{1}\beta ͺ\beta ͺ\right)$

• PartΒ (B) of FigureΒ 3.7.2 considers aΒ placement problem where we have both to assign a rectangle to a rectangular piece and to locate it within the selected rectangular piece. In this context the different potential rectangular pieces where rectangles can be placed is also called an assignment dimension. Note that in suchΒ placement problems the size of an object in an assignment dimension is always equal to one. This problem can be directly modelled by a $\mathrm{\pi \pi \pi \pi \pi }$ or a $\mathrm{\pi \pi \pi \pi \pi }$ constraint. The corresponding two ground instances encoding the example are (attributes related to the assignment dimension are shown in bold):

• $\mathrm{\pi \pi \pi \pi \pi }$$\left(\beta ©\mathrm{\pi \pi \pi \pi }-\beta ©\mathrm{\pi \pi \pi }-\mathbf{2}\mathrm{\pi \pi \pi £}-\mathbf{1}\mathrm{\pi \pi \pi }-\mathbf{3},$

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-2\mathrm{\pi \pi \pi £}-2\mathrm{\pi \pi \pi }-4,$

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-2\mathrm{\pi \pi \pi £}-2\mathrm{\pi \pi \pi }-4\beta ͺ,$

Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi \pi }-\beta ©\mathrm{\pi \pi \pi }-\mathbf{1}\mathrm{\pi \pi \pi £}-\mathbf{1}\mathrm{\pi \pi \pi }-\mathbf{2},$

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-3\mathrm{\pi \pi \pi £}-3\mathrm{\pi \pi \pi }-6,$

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-1\mathrm{\pi \pi \pi £}-2\mathrm{\pi \pi \pi }-3\beta ͺ,$

Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi \pi }-\beta ©\mathrm{\pi \pi \pi }-\mathbf{2}\mathrm{\pi \pi \pi £}-\mathbf{1}\mathrm{\pi \pi \pi }-\mathbf{3},$

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-6\mathrm{\pi \pi \pi £}-1\mathrm{\pi \pi \pi }-7,$

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-1\mathrm{\pi \pi \pi £}-3\mathrm{\pi \pi \pi }-4\beta ͺ\beta ͺ\right)$

• $\mathrm{\pi \pi \pi \pi \pi }$$\left(3,\beta ©\mathrm{\pi \pi \pi }-1\mathrm{\pi \pi \pi }-1\mathrm{\pi ‘}-\beta ©\mathbf{2},2,2\beta ͺ,$

Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-2\mathrm{\pi \pi \pi }-2\mathrm{\pi ‘}-\beta ©\mathbf{1},3,1\beta ͺ,$

Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-3\mathrm{\pi \pi \pi }-3\mathrm{\pi ‘}-\beta ©\mathbf{2},6,1\beta ͺ\beta ͺ$

Β Β Β Β Β Β Β Β Β Β $\beta ©\mathrm{\pi \pi \pi }-1\mathrm{\pi }-\beta ©\mathbf{0},0,0\beta ͺ\mathrm{\pi }-\beta ©\mathbf{1},2,2\beta ͺ,$

Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-2\mathrm{\pi }-\beta ©\mathbf{0},0,0\beta ͺ\mathrm{\pi }-\beta ©\mathbf{1},3,2\beta ͺ,$

Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-3\mathrm{\pi }-\beta ©\mathbf{0},0,0\beta ͺ\mathrm{\pi }-\beta ©\mathbf{1},1,3\beta ͺ\beta ͺ\right)$

• PartΒ (C) of FigureΒ 3.7.2 considers aΒ placement problem where we have both to assign a box to a Β container and to place it within the selected Β container. In this context the different potential Β containers where boxes can be packed is also called an assignment dimension. Note that in suchΒ placement problems the size of an object in an assignment dimension is always equal to one. This problem can be directly modelled by a $\mathrm{\pi \pi \pi \pi \pi }$ or a $\mathrm{\pi \pi \pi \pi \pi }$ constraint. The corresponding two ground instances encoding the example are (attributes related to the assignment dimension are shown in bold):

• $\mathrm{\pi \pi \pi \pi \pi }$$\left(\beta ©\mathrm{\pi \pi \pi \pi }-\beta ©\mathrm{\pi \pi \pi }-\mathbf{1}\mathrm{\pi \pi \pi £}-\mathbf{1}\mathrm{\pi \pi \pi }-\mathbf{2},$

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-1\mathrm{\pi \pi \pi £}-1\mathrm{\pi \pi \pi }-2,$

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-1\mathrm{\pi \pi \pi £}-2\mathrm{\pi \pi \pi }-3,$

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-1\mathrm{\pi \pi \pi £}-1\mathrm{\pi \pi \pi }-2\beta ͺ,$

Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi \pi }-\beta ©\mathrm{\pi \pi \pi }-\mathbf{1}\mathrm{\pi \pi \pi £}-\mathbf{1}\mathrm{\pi \pi \pi }-\mathbf{2},$

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-1\mathrm{\pi \pi \pi £}-1\mathrm{\pi \pi \pi }-2,$

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-1\mathrm{\pi \pi \pi £}-1\mathrm{\pi \pi \pi }-2,$

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-2\mathrm{\pi \pi \pi £}-1\mathrm{\pi \pi \pi }-3\beta ͺ,$

Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi \pi }-\beta ©\mathrm{\pi \pi \pi }-\mathbf{2}\mathrm{\pi \pi \pi £}-\mathbf{1}\mathrm{\pi \pi \pi }-\mathbf{3},$

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-1\mathrm{\pi \pi \pi £}-2\mathrm{\pi \pi \pi }-3,$

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-1\mathrm{\pi \pi \pi £}-2\mathrm{\pi \pi \pi }-3,$

Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-1\mathrm{\pi \pi \pi £}-1\mathrm{\pi \pi \pi }-2\beta ͺ\beta ͺ\right)$

• $\mathrm{\pi \pi \pi \pi \pi }$$\left(4,\beta ©\mathrm{\pi \pi \pi }-1\mathrm{\pi \pi \pi }-1\mathrm{\pi ‘}-\beta ©\mathbf{1},1,1,1\beta ͺ,$

Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-2\mathrm{\pi \pi \pi }-2\mathrm{\pi ‘}-\beta ©\mathbf{1},1,1,2\beta ͺ,$

Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-3\mathrm{\pi \pi \pi }-3\mathrm{\pi ‘}-\beta ©\mathbf{2},1,1,1\beta ͺ\beta ͺ$

Β Β Β Β Β Β Β Β Β Β $\beta ©\mathrm{\pi \pi \pi }-1\mathrm{\pi }-\beta ©\mathbf{0},0,0,0\beta ͺ\mathrm{\pi }-\beta ©\mathbf{1},1,2,1\beta ͺ,$

Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-2\mathrm{\pi }-\beta ©\mathbf{0},0,0,0\beta ͺ\mathrm{\pi }-\beta ©\mathbf{1},1,1,1\beta ͺ,$

Β Β Β Β Β Β Β Β Β Β Β $\mathrm{\pi \pi \pi }-3\mathrm{\pi }-\beta ©\mathbf{0},0,0,0\beta ͺ\mathrm{\pi }-\beta ©\mathbf{1},2,2,1\beta ͺ\beta ͺ\right)$

In summary, within the context of placement problems that use a constraint like $\mathrm{\pi \pi \pi \pi \pi }$ or $\mathrm{\pi \pi \pi \pi \pi }$, the coordinate of an object in the assignment dimension corresponds to the resource to which the object is assigned. Note that the size of an object in the assignment dimension is always set to 1. This stems from the fact that an object is assigned to a single resource.

Using constraints like $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi \pi }$, $\mathrm{\pi \pi \pi \pi \pi }$ or $\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$ allows to model directly with a single global constraint such problems without knowing in advance to which machine, to which rectangular piece, to which container, a task, a rectangle, a box will be assigned. For each object the potential values of its assignment variable provide the machines, the rectangular pieces, the Β containers to which the object can possibly be assigned. Note that this allows to avoid 0-1 variables for modelling such problems.

Within constraints like $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi }$ or $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }_\mathrm{\pi \pi \pi }$ the concept of assignment dimension is extended from the fact that a variable is assigned a value to the fact that a variable is assigned an interval (i.e., a value in an interval).