### 3.7.212. Relaxation dimension

modelling: relaxation dimension A constraint that allows the modelling of constraint relaxation in the context of placement problems. This is achieved by adding an extra dimension to the placement space where objects that are really considered are in the foreground, while objects that are discarded are rejected into the background. As a concrete example, consider a slight modification of the data of the task assignment and scheduling problem that is described at the keyword entry assigning and scheduling tasks that run in parallel. In this problem the four nurses are all not available during the time periods $\left[0,0\right]$, $\left[7,7\right]$, $\left[12,12\right]$ and $\left[22,22\right]$. We now rather consider the following unavailability periods $\left[0,0\right]$, $\left[8,8\right]$, $\left[12,12\right]$ and $\left[22,22\right]$. Under this new hypothesis we cannot anymore schedule all the five surgery tasks ${t}_{1}$, ${t}_{2}$, ${t}_{3}$, ${t}_{4}$ and ${t}_{5}$, i.e., we get a no solution answer if we use the model described in assigning and scheduling tasks that run in parallel. In this model we are using a two-dimensional $\mathrm{𝚐𝚎𝚘𝚜𝚝}$ constraint, where the first and second dimensions respectively correspond to the time and resource axes. Now, in order to permit relaxation, we introduce a third dimension, a relaxation dimension. The idea is to map each task to a parallelepiped for which the size in the relaxation dimension is equal to one. In addition, the coordinate of a parallelepiped in the relaxation dimension is a variable taking its value in the interval $\left[1,n\right]$, where $n$ represents the number of operations to schedule (i.e., for each surgery task ${t}_{i}$ $\left(1\le i\le n=5\right)$ we create a coordinate variable ${r}_{i}$ where $r$ stands for relaxation. Then, all parallelepipeds for which the coordinate in the relaxation dimension is set to 1 correspond to surgery tasks that are effectively scheduled, while all other parallelepipeds represent surgery tasks that are discarded. On the one hand, this model allows the direct expression of relaxation right from the beginning without introducing any extra soft constraint and without dynamically adding any constraint during search. On the other hand, a disadvantage is that the model does not directly consider an optimisation criterion like, for instance, the maximum number of tasks effectively scheduled, or the sum of the durations of the tasks effectively done; this can be modelled using extra constraints but this does not provide sharp bounds on the optimisation criterion. Nevertheless, this gives a compact model, especially in the context where additional constraints complicate the computation of a sharp bound. Going back to the example described at the keyword entry assigning and scheduling tasks that run in parallel, we get the following three-dimensional $\mathrm{𝚐𝚎𝚘𝚜𝚝}$ constraint: Figure 3.7.56 depicts a solution to the problem corresponding to the assignment $\begin{array}{cccccc}\mathrm{𝚝𝚊𝚜𝚔𝚜}\hfill & \mathrm{𝚘𝚛𝚒𝚐𝚒𝚗}\hfill & \mathrm{𝚛𝚎𝚕𝚊𝚡𝚊𝚝𝚒𝚘𝚗}\hfill & \mathrm{𝚊𝚗𝚊𝚎𝚜𝚝𝚑𝚎𝚝𝚒𝚜𝚝}\hfill & \mathrm{𝚜𝚞𝚛𝚐𝚎𝚘𝚗}\hfill & \mathrm{𝚗𝚞𝚛𝚜𝚎}\hfill \\ {t}_{1}\hfill & {o}_{1}=9\hfill & {r}_{1}=1\hfill & {a}_{1}=1\hfill & {s}_{1}=4\hfill & {n}_{11}=5,{n}_{12}=6\hfill \\ {t}_{2}\hfill & {o}_{2}=0\hfill & {r}_{2}=2\hfill & {a}_{2}=2\hfill & {s}_{2}=4\hfill & {n}_{2}=8\hfill \\ {t}_{3}\hfill & {o}_{3}=2\hfill & {r}_{3}=1\hfill & {a}_{3}=1\hfill & {s}_{31}=3,{s}_{32}=4\hfill & {n}_{31}=5,{n}_{32}=6\hfill \\ {t}_{4}\hfill & {o}_{4}=17\hfill & {r}_{4}=1\hfill & {a}_{4}=1\hfill & {s}_{4}=4\hfill & {n}_{41}=5,{n}_{42}=6,{n}_{43}=7\hfill \\ {t}_{5}\hfill & {o}_{5}=16\hfill & {r}_{5}=1\hfill & {a}_{5}=2\hfill & {s}_{5}=3\hfill & {n}_{5}=8\hfill \end{array}$

During search, the relaxation variables ${r}_{1}$, ${r}_{2}$, ${r}_{3}$, ${r}_{4}$, ${r}_{5}$ are first set to value one (i.e., the corresponding operations are scheduled) and then, upon backtracking, assigned to any value greater than one (i.e., there is no backtrack on the values that are greater than one since we just want to reject an operation into the background).

##### Figure 3.7.56. A partial solution to the surgery scheduling problem that maximises the number of operations actually performed where only operation ${t}_{2}$ is not scheduled 