🧩 Constraint Solving POTD:Problem of the Day: Nurse Rostering

[github-actions[bot]]

Problem Statement

Nurse rostering asks us to assign each nurse a shift for every day of a planning period so that the ward is staffed and labour rules are respected. Shifts are Day (D), Night (N), or Off (O).

Hard constraints (must hold):

• Exactly one Day nurse and exactly one Night nurse each day.
• Each nurse works between 2 and 3 shifts in the period.
• No Night shift directly followed by a Day shift (rest rule).

Soft constraint (minimise violations): honour each nurse's day-off requests.

Small instance: 3 nurses (Ann, Ben, Cy), 4 days. Ann asks for day 2 off.

Output: a roster that satisfies all hard constraints and minimises the number of violated requests.

One valid optimal roster (zero violated requests):

       day1 day2 day3 day4
Ann     D    O    D    D
Ben     N    N    N    O
Cy      O    D    O    N

Brute force over all 312 ≈ 531k assignments finds 222 feasible rosters, and this one meets Ann's request. You can check it by hand.

Why It Matters

• Hospitals and clinics: rosters are costly to build by hand and must balance coverage, fairness, and union or legal rules.
• Airlines and call centres: crew and agent scheduling follows the same pattern of cover demands plus work-rule constraints.

Real wards involve dozens to hundreds of staff and several skill types, and rosters are often rebuilt monthly. The Burke et al. survey (see References) catalogues the variants.

Modeling Approaches

Approach 1: Constraint Programming (CP)

• Variables: x[n,d] ∈ {D, N, O} for nurse n and day d.
• Constraints: cardinality constraints for daily cover (count(x[·,d] = D) = 1, likewise for N); a per-nurse cardinality on worked shifts; a regular (automaton) constraint for the rest rule.
• Trade-offs: very expressive, and the global constraints propagate strongly. Soft requests are handled by an objective, which CP solvers optimise with branch-and-bound or LNS. Proving optimality can be slow on large instances.

Approach 2: Mixed-Integer Programming (MIP)

• Variables: binary y[n,d,s] ∈ {0,1} with y[n,d,D] + y[n,d,N] + y[n,d,O] = 1.
• Constraints: Σn y[n,d,D] = 1 and Σn y[n,d,N] = 1 for daily cover; 2 ≤ Σ_d (1 − y[n,d,O]) ≤ 3 for worked shifts; y[n,d,N] + y[n,d+1,D] ≤ 1 for the rest rule.
• Objective: minimise the violated requests, here 1 − y[Ann,2,O] for Ann's request on day 2.
• Trade-offs: the LP relaxation gives a bound that proves optimality for soft objectives. Model size grows with nurses × days × shifts, and the rest-rule pairs add many rows.

Example Model (Pseudo-code, CP style)

Example Model (Pseudo-code)

N = 3; D = 4                       % nurses, days
shifts: 1 = Day, 2 = Night, 3 = Off
x[n,d] ∈ {1,2,3}                   % roster

for each d:
    sum_n bool2int(x[n,d] = 1) = 1 % exactly one Day nurse
    sum_n bool2int(x[n,d] = 2) = 1 % exactly one Night nurse

for each n:
    w_n = sum_d bool2int(x[n,d] != 3)
    2 ≤ w_n ≤ 3                    % worked shifts

for each n, d < D:
    not (x[n,d] = 2 ∧ x[n,d+1] = 1) % no Night → Day

x[Ann,2] = 3                       % request (hard here; make soft with a penalty)

Key Techniques

1. Global constraints with automata. The regular constraint (Pesant, 2004) encodes the whole sequence of shifts for one nurse as a DFA and gives generalised arc consistency. It removes many infeasible shift values before search, which is more effective than pairwise rest-rule clauses.

2. Search and learning. Use first-fail variable ordering (the day or nurse with fewest remaining feasible shifts) and value ordering that prefers satisfied requests. Lazy-clause-generation solvers such as CP-SAT add nogood learning and restarts, which handle the tightly coupled cover constraints well.

3. Symmetry breaking. Nurses with the same skills and no requests are interchangeable. Lex-order their rows (lex-leader constraints) to avoid exploring equivalent rosters several times.

Challenge Corner

• Can you find a request set that forces a positive minimum penalty? Start from the instance above and add requests for Ben and Cy until no zero-penalty roster exists.
• Model the rest rule with fewer variables. Can a DFA over the shift sequence replace the pairwise N → D constraints without losing propagation?
• Add a weekend rule (each nurse works at most one weekend in two). Which of the two models above absorbs the extra constraint more easily, and why?

References

• Burke, E. K., De Causmaecker, P., Vanden Berghe, G., & Van Landeghem, H. (2004). The State of the Art of Nurse Rostering. Journal of Scheduling, 7(6), 441–499.
• Pesant, G. (2004). A Regular Language Membership Constraint for Finite Sequences of Variables. CP 2004.
• Beldiceanu, N., Carlsson, M., & Rampon, J.-X. (2005). Global Constraint Catalog. SICS Technical Report. (See the regular and cardinality entries.)
• Google OR-Tools CP-SAT documentation: (developers.google.com/redacted)

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · routed: haiku55 xhigh · ~2 AIC · ⌖ ~2 AIC · ⊞ 4.1K · ◷

• expires on Nov 16, 2026, 3:31 AM UTC-08:00

[github-actions[bot]]

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

A newer discussion is available at Discussion #76498.