Chvátal–Gomory Cuts Applied to the Nurse Rostering Problem

The nurse rostering problem (NRP) has attracted significant research interest in recent decades due to both its practical relevance and computational complexity. While the branch-and-price algorithm has demonstrated effectiveness in solving NRPs, its column generation component frequently produces weak lower bounds for some problem instances, which consequently degrades overall computational performance. To strengthen the lower bound quality, we propose three classes of cutting planes derived from the column generation master problem formulation: SRCs, CG rank-1 cuts, and {0, ½}-cuts. For each cut type, the separation approaches enhanced with acceleration strategies are described. These cuts are typically classified as non-robust, meaning each cut added to the master problem requires introducing a new resource in the pricing subproblem’s labeling algorithm. We therefore developed problem-specific methods to update these resources and integrate them into the NRP dominance rules. Computational experiments were conducted on benchmark instances from two international nurse rostering competitions (INRC-I and INRC-II). The results indicate that SRCs are highly effective for two challenging INRC-I instances, including one where a tighter lower bound was identified. In contrast, the {0, ½}-cuts yield the strongest performance for most selected INRC-II instances. These findings demonstrate that the cutting plane method can be used to improve lower bounds for NRPs, and that the effectiveness of different cut types in improving lower bounds is closely tied to the problem formulation.