

![0_image_0.png](0_image_0.png)

![0_image_1.png](0_image_1.png)

example, in Fig 3, two rows (schedules for nurses C and F) with the highest cost are chosen and added

![0_image_2.png](0_image_2.png)

![0_image_3.png](0_image_3.png) to the fragment.

The size of column (length of the selected rows) added to the fragment is decided by the information gained from constraint propagation. The idea is that when a variable is relaxed and re-initialized, propagation occurs. By tracing the volume of domain reduction, we can detect which variables are linked to the relaxed variables and use this information to determine the next variable to relax. The complete method using strategy 3 is described in Table 2. For each soft constraint c a variable list is maintained storing the variables linked by this constraint. Both the size of this list and the way it is updated are parameters of this algorithm. In our experiment, the variable list is consists of variables linked by the constraint involved and variables propagated by this constraint. We set the size of the list as 7 (due to the weekly structure in the roster). We also notice that the list is almost always full in the experiments, indicating that the dependencies of variables are quite tight, i.e. highly constrained. The algorithm loops until the size of fragment's search space is reasonable large.

A possible extension of the algorithm may be made to further improve the LNS search. Instead of a fixed fragment of size s, we can adjust the desired fragment size s by adding a multiplicative correction factor to s, i.e. fragment of size set as s×ε, where ε is continuously updated throughout the search process. Future investigations will be carried out to analyze the performance of the approach with different