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

[github-actions[bot]]

Daily problem from the constraint solving world — 2026-03-31 · Category: Scheduling

---

Problem Statement

A hospital must assign nurses to shifts over a planning horizon (typically one to four weeks). Each shift is one of Day (D), Evening (E), or Night (N), and there is also an Off (O) option. Nurses have different skill levels, contracts, and personal preferences. The scheduler must respect hard rules (safety, labor law) and optimize soft objectives (fairness, preference satisfaction).

Concrete Instance (5 nurses, 7 days)

Nurses: Alice, Bob, Carol, Dan, Eve
Shifts: D (07–15h), E (15–23h), N (23–07h), O (off)
Days:   Mon … Sun

Hard constraints:
  • Each shift type needs ≥ 1 nurse per day
  • No nurse works more than 5 shifts per week
  • No nurse works a Night shift directly followed by a Day shift
  • Each nurse gets ≥ 2 days off per week

Soft objectives (minimize):
  • Deviation from requested days off
  • Understaffing on any shift
  • Unfair distribution of Night shifts
```

**Input:** nurse profiles, shift demands, contract rules, preferences  
**Output:** an assignment `roster[nurse][day] ∈ {D, E, N, O}` satisfying all hard constraints and minimising the weighted soft-constraint violations.

---

### Why It Matters

**Healthcare operations** — Poor rosters lead to staff burnout and care-quality issues; an optimized schedule can reduce overtime costs by 10–20% while improving nurse satisfaction scores.

**Labor-law compliance at scale** — Hospitals employ hundreds of nurses across dozens of wards. Manual scheduling is error-prone and typically takes days; automated solvers can generate compliant rosters in minutes.

**Benchmark domain** — Nurse rostering is a canonical benchmark for CP, MIP, and metaheuristics. The [INRC (International Nurse Rostering Competition)]((nurserostering.com/redacted) has run multiple editions (2010, 2015) providing standardized instances.

---

### Modeling Approaches

#### Approach 1 — Constraint Programming (CP)

**Decision variables:**  
`roster[n][d] ∈ {D, E, N, O}` for each nurse `n ∈ 1..N`, day `d ∈ 1..H`

**Key constraints (hard):**
```
∀d: |{n | roster[n][d] = D}| ≥ demand_D[d]     # staffing
∀d: |{n | roster[n][d] = E}| ≥ demand_E[d]
∀n, d: roster[n][d] = N → roster[n][d+1] ≠ D   # no N→D sequence
∀n: sum(d: roster[n][d] ≠ O) ≤ max_shifts[n]    # contract
```

**Objective:** minimise weighted sum of soft-constraint violations (modelled as auxiliary integer variables with penalties).

**Trade-offs:** CP excels at expressing complex sequence constraints (e.g., forbidden patterns) via automaton/regular constraints. Propagation can prune large parts of the search space quickly. Scales well to medium instances (≤ 100 nurses, ≤ 28 days) with good variable ordering.

---

#### Approach 2 — Mixed-Integer Programming (MIP)

**Binary decision variables:**  
`x[n][d][s] ∈ {0,1}` — nurse `n` is assigned shift `s` on day `d`

**Key constraints:**
```
∀n,d:   Σ_s x[n][d][s] = 1                         # exactly one shift per (nurse,day)
∀d,s:   Σ_n x[n][d][s] ≥ demand[d][s]               # coverage
∀n,d:   x[n][d][N] + x[n][d+1][D] ≤ 1               # no N→D
∀n:     Σ_{d,s≠O} x[n][d][s] ≤ max_shifts[n]

Objective: minimise Σ penalty_k * violation_k (LP relaxation provides a lower bound).

Trade-offs: MIP solvers (Gurobi, HiGHS, CPLEX) provide proven optimality gaps and excellent LP relaxation bounds. However, modeling complex sequential patterns requires many auxiliary binary variables, which can slow root-node LP solve. MIP typically outperforms CP on large, loosely-constrained instances.

---

Approach 3 — Local Search / Metaheuristics

Start from any feasible (or near-feasible) assignment and iteratively improve by applying moves:

• Swap move: exchange shifts between two nurses on the same day
• Block move: shift a nurse's pattern by one day

Used in practice (e.g., simulated annealing, tabu search) for very large instances where exact methods time out. Trade-off: no optimality guarantee, but can find good solutions quickly for 500+ nurses.

---

Example Model — MiniZinc (CP)

int: N;  % number of nurses
int: H;  % planning horizon (days)
array[1..N, 1..H] of var 0..3: roster;
% 0=Off, 1=Day, 2=Evening, 3=Night

% Demand coverage (Day shift, day 1 needs >=2)
array[1..H] of int: demand_day;
constraint forall(d in 1..H)(
  sum(n in 1..N)(roster[n,d] == 1) >= demand_day[d]
);

% No Night followed by Day
constraint forall(n in 1..N, d in 1..H-1)(
  not (roster[n,d] == 3 /\ roster[n,d+1] == 1)
);

% At most max_shifts shifts per week (days 1..7)
int: max_shifts = 5;
constraint forall(n in 1..N)(
  sum(d in 1..min(7,H))(roster[n,d] != 0) <= max_shifts
);

% Soft: penalise understaffing on Evening shifts
array[1..H] of var 0..N: understaffing_eve;
constraint forall(d in 1..H)(
  understaffing_eve[d] = max(0,
    demand_eve[d] - sum(n in 1..N)(roster[n,d] == 2))
);

var int: obj = sum(d in 1..H)(understaffing_eve[d]);
solve minimize obj;

---

Key Techniques

1. Global Constraints for Sequences

The regular (or automaton) global constraint in CP can encode any forbidden shift pattern expressible as a DFA. For nurse rostering, this is used to enforce rules like "no more than 3 consecutive nights" or "at least 2 days off after a night block" in a single, efficiently propagated constraint — far more scalable than individual binary constraints.

2. Column Generation (MIP)

For large instances, a Dantzig–Wolfe decomposition treats each nurse's complete weekly pattern as a column. The master problem selects a set of patterns (one per nurse) satisfying coverage. The pricing subproblem (a shortest-path or CP sub-problem per nurse) generates improving patterns. This dramatically reduces the MIP size and often finds high-quality solutions quickly.

3. Symmetry Breaking

Nurses with identical skill profiles and contracts are interchangeable. Adding lexicographic ordering constraints (e.g., roster[1] ≤_lex roster[2] for equivalent nurses) eliminates symmetric solutions and can reduce search by orders of magnitude.

---

Challenge Corner

Extension — Stochastic Demand:
In practice, demand is uncertain (sick calls, emergencies). Can you model nurse rostering as a two-stage stochastic program — a fixed base roster in stage 1 and recourse assignments (overtime, swaps) in stage 2? How would you handle the exponential number of scenarios efficiently?

Bonus: What symmetry-breaking constraints remain valid when nurses are no longer interchangeable due to seniority-based overtime preferences?

---

References

1. Cheang et al. (2003). "Nurse rostering problems — a bibliographic survey." European Journal of Operational Research, 151(3), 447–460. — Comprehensive survey of the domain.
2. Haspeslagh et al. (2014). "The first international nurse rostering competition 2010." Annals of Operations Research, 218(1), 221–236. — Benchmark instances and competition results.
3. Van den Bergh et al. (2013). "Personnel scheduling: A literature review." European Journal of Operational Research, 226(3), 367–385. — Broader workforce scheduling context.
4. Rossi, van Beek & Walsh (2006). Handbook of Constraint Programming, Elsevier. — Chapter 18 covers scheduling constraint models in depth.

AI generated by Constraint Solving — Problem of the Day · history

• expires on Apr 7, 2026, 12:55 PM UTC