An Advanced Answer Set Programming Encoding for Nurse Scheduling

The goal of the Nurse Scheduling Problem (NSP) is to find an assignment of nurses to shifts according to specific requirements. Given its practical relevance, many researchers have developed different strategies for solving several variants of the problem. One of such variants was recently addressed by an approach based on Answer Set Programming (ASP), obtaining promising results. Nonetheless, the original ASP encoding presents some intrinsic weaknesses, which are identified and eventually circumvented in this paper. The new encoding is designed by taking into account both intrinsic properties of NSP and internal details of ASP solvers, such as cardinality and weight constraint propagators. The performance gain of CLINGO and wasp is empirically verified on instances from ASP literature. As an additional contribution, the performance of CLINGO and wasp is compared to other declarative frameworks, namely SAT and ILP; the best performance is obtained by CLINGO running the new ASP encoding.