The Nurse scheduling problem is recognized to be very challenging as it must generally propose a personalized schedule for every nurse. The talk will focus on the deterministic counterpart of the specific problem that has been described in the second international nurse rostering competition (INRC-II). One specificity of this version is that most constraints are soft, meaning that they can be violated at the price of a penalty. Classical branch-and-price algorithms underperform with soft constraints in the subproblems as they generally solve a classical resource-constrained shortest-path. In this talk, I will present a different approach to implement more aggressive domination functions for soft constraints. This new method allows solving efficiently at optimality many instances from the INRC-II involving up to 120 nurses and 4 shifts over a 4 to 8-weeks horizon. Different models and features will be presented, and many computational results will compare the different approaches.