Table 2: The constraint directed large neighborhood search approach using strategy 3 While Fragment size is smaller than the desired size s If variable list is empty then Randomly choose a linked variable Else choose a variable in the variable list End if Reinitialize the chosen variable and propagate Update the variable list: add propagated variables to the list End if End while sizes of the fragment, i.e. the fixed desired size s and the desired adjusted size s×ε.

## 3.4 Searching Heuristics

After the fragment has been chosen by either the problem specific strategies or the general strategy, the variables in the fragment are relaxed and re-optimized while all other variables are frozen to their existing assignments. The standard branch-and-bound (B&B) search in constraint programming is used with respect to the objective function for the whole problem, i.e. sum of violations as defined in section 2.2. Within the B&B search, we compare two variable selection heuristics to search for the optimal solution for the chosen fragment.

As shown in Table 1, when we re-optimize the chosen fragment, we can either follow the first improved rule or the best improved rule. First improved rule stops the optimization procedure as soon as the first improved solution is found; while the best improved rule solves the problem to optimal. We use the best improved rule on small size problems and the first improved rule on large size problems.

## 4 Experimental Results

In this work, we evaluate our constraint-directed LNS upon a benchmark nurse rostering problem GPost, public available at http://www.cs.nott.ac.uk/∼tec/NRP. The problem consists of 8 nurses who work on 3 different shift types over a scheduling period of 28 days. Other problems with different characteristics will be tested in our future work. In all experiments, 10 runs are carried out on an Intel Core 1.86GHz machine with 1.97G memory, from which average results are presented. We use the callable library in ILOG solver 6.2 as the CP solver and implement all algorithms in C++.

## 4.1 Search Heuristics

We first test several variable selection heuristics to identify the efficient search heuristics in re-optimizing the chosen fragment. The variable order heuristics include:
- MinSizeInt: chooses the variable with the smallest domain

- MaxSizeInt: chooses the variable with the largest domain - MinMinInt: chooses the variable with the least minimal bound
- MaxMinInt: chooses the variable with the greatest minimal bound