Table 1: The large neighborhood search scheme Stage 1: construct initial solution: solve (H) // H: set of hard constraints Stage 2: *While* optimal solution not found or stopping criteria not met do //LNS
Choose the low quality fragment to be relaxed Freeze the remaining variables Re-optimize the fragment with strategy i // see sections 3.1-3.3 If found (a) First improved solution, or
(b) Best improved solution // search heuristics, see section 3.4 Update solution End if End while the initial solution. The LNS is parameterized with different strategies to choose the low quality fragment (poor assignment) in the solution, which is relaxed and re-optimized to obtain improved solutions iteratively.

As observed by several researchers [14, 15], the key issue in designing efficient LNS is the selection of the fragment, i.e. set of variables to be relaxed and re-optimized. For instance, in job shop scheduling problems, the fragments usually involve the critical path of the schedules. In routing problems, cluster removing techniques have been used. To a certain extent, the success of LNS depends on the adequacy of this fragment (neighbourhood) with regard to the problematic parts of the solution and the choice of the neighbourhood size.

The roster (solution) we construct for NRPs has a 2-Dimensional row/column structure. Each row represents the schedule for a nurse and each column represents a day assignment in the scheduling period. The constraints involved in the model can thus be categorized as row/horizontal constraints and column/vertical constraints. In our problem, there is only one hard constraint, coverage constraint, which can be seen as a column constraint. All other constraints concerning shift patterns and preferences can be seen as row constraints. This 2-Dimensional structure of rosters determines the basic structure of the fragment selected. That is, we can select related variables by choosing which row and which column of variables to be added to the fragment.

The advantages of choosing small fragments are that complete assignment can be searched quickly.

However, it is more likely that an improved solution exists in larger fragments. There is thus a trade-off between the computational time and the optimality while we set the size of the chosen fragment. Ideally the fragment should be large enough to have a reasonable chance of moving to an improved solution, and small enough so computational time is affordable.

We investigate three strategies in this paper to choose the fragment of variables. The first two strategies are based on the observations that specific neighbourhoods with domain knowledge are usually helpful in finding good results. The first basic strategy iteratively chooses all rows (schedules of all nurses) with a fixed length over the roster, i.e. a sliding window covering fixed days/columns of the roster for all nurses. The second strategy considers the overlap of these sliding windows. In addition, a more general third strategy is investigated by using the information gained via constraint propagation to define the fragment (neighbourhood). It chooses the fragment with respect to the cost of global soft constraints, and thus is more general compared with the first two strategies.