Algorithm performance prediction for nurse rostering

In this paper, we investigate accurate performance prediction models for nurse rostering algorithms. The study is based on results of a similar approach for formally stated decision problems. Due to the complex nature of nurse rostering problems, we are bound to use heuristic methods that deliver good solutions in a reasonable amount of time. There is no guarantee of solutions being optimal. In practice, it is not even possible to employ exhaustive search methods on realistic problem instances. We quantify the performance of an algorithm as the quality of the obtained solution, after a predetermined amount of computation time. We build prediction models based on simple characteristics of the instances. We develop a feature set that characterises the instances in terms of simple values. Such an approach al- lows for fast and accurate predictions. The application of the methodology to nurse rostering has not been attempted before.status: publishe