usually applied to improve initial complete solutions obtained from a construction phase in terms of the cost of the solutions, i.e. the value of the objective function. Roughly speaking, we can categorize local search approaches into two types: traditional local search and constraint-directed local search approaches.

Traditional local search approaches employ neighbourhood moving operators, such as 2-opt, k-opt and ejection chain, etc, while the satisfaction of constraints are checked at each move [3]. The moves considered are usually only those preserving the feasibility, i.e. all constraints have been satisfied. These methods are thus lack of flexibility when moving in the search space because the search is more likely to be stuck in the region around the initial solution. Meyer auf'm Hofe [12] highlights this limitation by using a specific example where the swap neighbourhood operator is unlikely to remove a particular violation, as it requires a simultaneous change of eight specific variables. One solution to resolve this limitation is to design more complex neighbourhood moves which amend larger parts of the current assignment. Dowsland [10] employs two types of ejection chains which consist of a sequence of on/off day swaps. Louw et al. [13] employ compound moves which are similar to the idea of chain swaps. These complex moves, although highly effective, face the potential problem of exploring an exponentially large neighbourhood. Complex moves which remain polynomial time solvable are highly desired, and usually are tailored to the specific properties of the problems in hand.

In constraint directed local search approaches, a more general neighbourhood move can be performed by using a complete search solver concerning all constraints involved. This is the central idea of large neighbourhood search (LNS) [9,14-17]. Inspired by the concept of the impact of a variable in integer programming techniques, Refalo in [18] proposed a general impact based strategy in constraint programming to measure the importance of a variable for a reduction of the search space. Laurent Perron in
[15] studied propagation guided large neighborhood search approaches. An adaptive large neighborhood search approach was proposed in [14] to solve vehicle routing problems by adaptively choosing among a number of insertion and removal heuristics (neighborhood structures) to intensify and diversify the search.

In this paper, we develop and investigate a constraint-directed local search approach within a LNS
scheme to tackle the NRPs. To the best of our knowledge, this is the first attempt to use this technique to NRPs. The two main advantages of this approach are: firstly, there is no need to design complicated neighbourhood move operators to reach more solutions in the search space; secondly, by using the branch and bound search in constraint programming, more than one variable assignment can be optimized within one improvement step.

The paper is organized as follows. In section 2 we describe the NRPs and build the constraint programming model with primitive constraints, global hard constraints and global soft constraints. In section 3 we present the constraint-directed LNS with different strategies. In section 4 we analyze computational experiment results. Conclusions and future work are given in section 5.

## 2 Problem Description And Modeling 2.1 Description Of The Nurse Rostering Problem

The NRPs we are testing are derived from real-world problems in intensive care units at hospitals. The problem consists of assigning a predefined number of shifts of different types (i.e. Early, Day, Night, Late) to a number of nurses of different working contracts in a hospital ward over a scheduling period (i.e. four weeks). Among the set of benchmark problems, the main constraints are similar but variants exist with respect to the number of nurses, number of shift types, length of the scheduling period, and