🧩 Constraint Solving POTD:Nurse Rostering — Scheduling Under Hard and Soft Constraints

[github-actions[bot]]

Today's problem sits at the intersection of real-world impact and rich constraint structure: Nurse Rostering (also called the Nurse Scheduling Problem, NSP). It's a canonical benchmark for constraint-based scheduling and a favourite in CP/OR competitions.

---

Problem Statement

A hospital must assign nurses to shifts over a planning horizon (typically 1–4 weeks) while satisfying a mix of hard requirements and soft preferences.

Small concrete instance — 4 nurses, 3 shifts/day (morning M, afternoon A, night N), 7 days:

	Mon	Tue	Wed	Thu	Fri	Sat	Sun
Alice	M	A	—	N	M	—	A
Bob	A	M	N	—	—	M	N
Carol	—	N	M	A	N	A	—
Diana	N	—	A	M	A	N	M

Input:

• n nurses, d days, shift types S = {M, A, N, Off}
• Coverage requirements: req[day][shift] = minimum nurses needed
• Contracts per nurse: max hours/week, forbidden shift sequences, requested days off, etc.

Output: An assignment roster[nurse][day] ∈ S that satisfies all hard constraints and minimises violations of soft constraints (weighted penalty).

---

Why It Matters

• Healthcare operations: Poor rosters lead to nurse burnout, understaffing during critical periods, and increased medical errors — this is a life-critical optimisation problem solved daily in thousands of hospitals.
• Regulatory compliance: Labour laws (rest periods, maximum consecutive nights, overtime) translate directly into hard constraints, making automated constraint-based solvers indispensable.

---

Modeling Approaches

Approach 1 — Constraint Programming (CP)

Decision variables: x[n, d, s] ∈ {0, 1} — nurse n works shift s on day d.

Key hard constraints:

# Each nurse works at most one shift per day
∀n, d:  ∑_s x[n,d,s] ≤ 1

# Coverage: minimum nurses per shift per day
∀d, s:  ∑_n x[n,d,s] ≥ req[d][s]

# No "night then morning" transition (forbidden sequence)
∀n, d:  x[n,d,N] + x[n,d+1,M] ≤ 1

# Max consecutive working days (e.g., ≤ 5)
∀n, d:  ∑_{k=0}^{5} (1 - x_off[n, d+k]) ≤ 5

Soft constraints become a weighted objective:

minimise  ∑_n ∑_d  w_pref · violation[n,d]  +  w_cover · under_cover[d,s]

Trade-offs: CP excels at propagating forbidden-sequence constraints via automaton/regular global constraints and handles complex nurse-specific rules naturally. Search can be slow on large instances without good heuristics.

Approach 2 — Mixed-Integer Programming (MIP)

Same binary variables but the model is handed to a MIP solver (CPLEX, Gurobi).

Key difference — shift pattern columns: Instead of day-by-day variables, enumerate feasible weekly patterns per nurse (each pattern is a sequence of shifts satisfying individual hard constraints). Use a set-covering formulation:

∀p ∈ patterns_n:  y[n,p] ∈ {0,1}   (nurse n assigned pattern p)

∑_p y[n,p] = 1           ∀n          (each nurse gets exactly one pattern)
∑_n ∑_p a[p,d,s]·y[n,p] ≥ req[d,s]  ∀d,s   (coverage met)

Trade-offs: LP relaxation gives strong lower bounds; column generation scales well when the pattern space is huge. Less natural for nurse-specific preference constraints that interact across nurses.

Example Model — MiniZinc snippet (CP approach)

int: N; int: D;  % nurses, days
set of int: SHIFTS = 0..3;  % 0=Off,1=M,2=A,3=N
int: OFF=0; int: MORNING=1; int: AFTERNOON=2; int: NIGHT=3;

array[1..N, 1..D] of var SHIFTS: roster;

% Coverage
constraint forall(d in 1..D)(
  sum(n in 1..N)(roster[n,d] == MORNING) >= req[d, MORNING]
);

% No night -> morning transition
constraint forall(n in 1..N, d in 1..D-1)(
  not (roster[n,d] == NIGHT /\ roster[n,d+1] == MORNING)
);

% Max 5 consecutive working days
constraint forall(n in 1..N, d in 1..D-5)(
  sum(k in 0..5)(roster[n,d+k] != OFF) <= 5
);

% Soft: penalise unmet preferences (using auxiliary penalty vars)
var int: penalty = sum(n in 1..N, d in 1..D)(
  bool2int(roster[n,d] != preferred[n,d]) * weight[n,d]
);
solve minimize penalty;

---

Key Techniques

1. Global Constraints — regular and sequence

Shift sequences (e.g., "no more than 3 nights in a row", "at least 2 days off after a night block") are perfectly expressed as regular language constraints. The regular(roster[n,..], automaton) global constraint propagates these efficiently via arc consistency on the sequence automaton — far stronger than posting individual binary constraints.

2. Variable/Value Ordering Heuristics

• Minimum remaining values (MRV): assign the nurse-day pair with fewest feasible shifts first.
• Least-constrained value: prefer shift assignments that leave the most flexibility for remaining nurses, especially for coverage requirements.
• Large Neighbourhood Search (LNS): fix most of the roster, destroy a random neighbourhood (e.g., one nurse's week), and re-solve. Extremely effective for large instances where complete search is infeasible.

3. Symmetry Breaking

If nurses share identical contracts, permuting them produces equivalent solutions. Add lexicographic ordering constraints on nurse assignment vectors:

lex_lesseq(roster[1,..], roster[2,..])  % if nurse 1 and 2 are symmetric

This alone can reduce search space by k! for k symmetric nurses.

---

Challenge Corner

🧩 Extension: In the International Nurse Rostering Competition (INRC), instances include "shift-on-request" and "shift-off-request" preferences at different weight levels, plus complex minimum/maximum consecutive constraint patterns per contract type.

Question: How would you encode a constraint like "nurse must have at least one full weekend off every 3 weeks" using the regular global constraint? What does the automaton look like, and can you express it more compactly using the sequence or sliding_sum global constraint instead?

---

References

1. Burke et al. (2004) — "The State of the Art of Nurse Rostering", Journal of Scheduling — the canonical survey covering complexity results and solution approaches.
2. Haspeslagh et al. (2014) — "The First International Nurse Rostering Competition 2010", Annals of Operations Research — benchmark instances and competition results.
3. Rossi, van Beek & Walsh (2006) — Handbook of Constraint Programming, Elsevier — Chapter 13 covers scheduling models and global constraints.
4. INRC-II benchmark instances: (www.inrc2.ugent.be/redacted) — standard test set used by researchers and solver vendors.

Generated by Constraint Solving — Problem of the Day · ● 112.3K · ◷

• expires on May 4, 2026, 1:08 PM UTC

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #28942.