73. Efficient constraint evaluation for the nurse rostering problem
Invited abstract in session TE-2: Timetabling, stream Timetabling.
Thursday, 16:30 - 18:00Room: M228
Authors (first author is the speaker)
| 1. | Robin Tourlamain
|
| KU Leuven |
Abstract
Local search algorithms are often used to generate solutions for numerous combinatorial optimisation problems. The effectiveness of such algorithms relies on their solution acceptance criterion, neighbourhood definitions, iteration speed, and other parameters. Our research focuses on the importance of efficient solution evaluation in local search algorithms, specifically in the context of the nurse rostering problem. Publications often overlook reporting this facet of their algorithms, even though it is integral to the reproducibility of the results. Indeed, as we will demonstrate, how one chooses to evaluate solutions is a highly consequential design decision and has a significant impact on the effectiveness of an algorithm. This is because the majority of computation time is spent evaluating new solutions, as calculating penalties for violated constraints is a complex task. Accelerating this process allows local search algorithms to perform more iterations, thereby improving solution quality.
In this talk we will introduce an efficient delta-evaluation method which reduces the number of necessary computations to a minimum. Re-using roster information from previous iterations enables us to safely ignore unaffected sections of the roster, and focus only on the modified part. Consequently, the worst-case performance of our method is equal to that of what is traditionally implemented, which evaluates the entire roster every time. Preliminary results indicate that this worst-case behaviour is a rare occurrence, as our method outperforms the traditional approach in terms of evaluation speed on every instance from the KaHo dataset [1].
1. Bilgin, B. et al. Local search neighbourhoods for dealing with a novel nurse rostering model. Annals of Operations Research 194, 33–57 (2012). https://doi.org/10.1007/s10479-010-0804-0
Keywords
- Combinatorial Optimization
- Scheduling
Status: accepted
Back to the list of papers