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

[github-actions[bot]]

Problem Statement

Nurse rostering (or nurse scheduling) is the problem of assigning nurses to shifts over a planning horizon while satisfying hard constraints (coverage, legal requirements) and minimizing violations of soft constraints (preferences, fairness).

Concrete Instance

A hospital has:

• 7 nurses: N1, N2, N3, N4, N5, N6, N7
• 14 days (2 weeks)
• 3 shifts per day: Morning (6am–2pm), Afternoon (2pm–10pm), Night (10pm–6am)
• Minimum coverage: 2 nurses per shift
• Hard constraints:
  • Each nurse works at most 5 shifts per week
  • No nurse works 3+ consecutive night shifts
  • Each nurse has ≥1 day off per week
• Soft constraints (minimize violations):
  • Prefer to avoid isolated days off
  • Balance shift types across the month
  • Respect individual availability preferences

Input/Output Specification

Input: Nurses, shifts, days, coverage requirements, constraint parameters
Output: A roster (assignment of nurses to shifts) that satisfies all hard constraints and minimizes soft constraint violations

---

Why It Matters

Healthcare Operations: Hospitals and care facilities manage thousands of staff globally. Poor rostering wastes labor, burnout leads to high turnover, and understaffing risks patient safety.

Service Industry: Airlines, call centers, and retailers use similar rostering to manage 24/7 operations while controlling labor costs and employee satisfaction.

Compliance & Fairness: Labor laws regulate maximum weekly hours, mandatory rest periods, and shift sequences—violations incur legal liability and reputational damage.

---

Modeling Approaches

Approach 1: Constraint Programming (CP)

Paradigm: Declarative constraint satisfaction with strong propagation.

Decision Variables:

• assign[n, d, s] ∈ {0, 1} for each nurse n, day d, shift s
  • 1 if nurse n is assigned to shift s on day d; 0 otherwise
• off[n, d] ∈ {0, 1} derived: off[n, d] = 1 - max(assign[n, d, s] for all shifts s)

Key Constraints (pseudo-code):

for each shift s and day d:
  sum(assign[n, d, s] for all nurses n) ≥ MIN_COVERAGE
  
for each nurse n and week w:
  sum(assign[n, d, s] for all d ∈ week w and shifts s) ≤ MAX_SHIFTS_PER_WEEK
  
for each nurse n:
  no_three_consecutive_nights(assign[n, :, Night])
  
global_cardinality([off[n, :] for each nurse n], cardinalities)

Trade-offs:

• ✅ Strong global constraints (e.g., global_cardinality) and propagation
• ✅ Natural modeling of soft preferences via objective function
• ❌ May need careful tuning for large instances (100+ nurses, months-long horizons)

Propagation Techniques: Arc consistency, bounds consistency, specialized propagators for cumulative and sequence constraints.

Approach 2: Mixed-Integer Programming (MIP)

Paradigm: Linear objective and constraints, solved via branch-and-cut.

Decision Variables:

• Same assign[n, d, s] binary variables
• Auxiliary variables for consecutive-day tracking, penalty counters

Key Constraints (linear inequalities):

for each shift s and day d:
  sum(assign[n, d, s] for n) ≥ MIN_COVERAGE
  
for each nurse n and week w:
  sum(assign[n, d, s] for d ∈ w, s) ≤ MAX_SHIFTS_PER_WEEK
  
no_consecutive_nights via:
  assign[n, d, Night] + assign[n, d+1, Night] + assign[n, d+2, Night] ≤ 2

Objective (linear combination):

minimize:  
  penalty_understaffed × (shifts with <MIN_COVERAGE)
  + penalty_preference × (unmet nurse preferences)
  + penalty_imbalance × (shift type variance)

Trade-offs:

• ✅ Mature solvers (CPLEX, Gurobi, HiGHS) with proven scalability
• ✅ Straightforward to encode coverage and shift limits
• ❌ Sequence constraints are unwieldy; requires auxiliary variables and big-M formulations
• ❌ Soft constraints force linearization (harder to express fairness naturally)

Example MiniZinc Model

int: num_nurses = 7;
int: num_days = 14;
int: num_shifts = 3;
int: min_coverage = 2;

array[1..num_nurses, 1..num_days, 1..num_shifts] of var 0..1: assign;

% Coverage constraints
constraint forall(d in 1..num_days, s in 1..num_shifts) (
  sum(n in 1..num_nurses) (assign[n, d, s]) >= min_coverage
);

% Max shifts per week
constraint forall(n in 1..num_nurses) (
  sum(d in 1..7) (assign[n, d, 1] + assign[n, d, 2] + assign[n, d, 3]) <= 5,
  sum(d in 8..14) (assign[n, d, 1] + assign[n, d, 2] + assign[n, d, 3]) <= 5
);

% No 3 consecutive night shifts (shift 3 = night)
constraint forall(n in 1..num_nurses, d in 1..12) (
  assign[n, d, 3] + assign[n, d+1, 3] + assign[n, d+2, 3] <= 2
);

solve minimize sum(n in 1..num_nurses, d in 1..num_days) (1 - (assign[n, d, 1] + assign[n, d, 2] + assign[n, d, 3]));

---

Key Techniques

1. Global Constraints for Scheduling

The cumulative and element global constraints, plus custom reified propagators, encode shift sequences and coverage efficiently. Many CP solvers provide domain-specific library predicates (e.g., no_overlap, atmost_consecutive).

2. Hybrid CP/Relaxation

Relax the problem to a network-flow subproblem (shift capacity × nurse availability) to find lower bounds; use these bounds to prune CP search. Alternatively, solve a relaxed MIP, then refine with CP-based local search.

3. Symmetry Breaking & Diversification

Nurse identity is often irrelevant—many equivalent solutions exist. Break symmetry by ordering nurses lexicographically or by preference strength. Use restart strategies (e.g., rapid restarts with perturbation) to escape local optima.

---

Challenge Corner

1. Can you encode fairness without explicit soft penalties? Many hospitals measure fairness as "least-max" variance in workload across nurses over a rolling 4-week window. How would you model this as a bottleneck optimization (minimize the maximum any nurse is overloaded)?

2. Extending to uncertainty: In reality, nurses call in sick, and demand fluctuates. How would you reformulate this as a stochastic or robust scheduling problem? Should you pre-assign "on-call" slots to absorb randomness?

3. Multi-objective trade-off: How do you balance coverage reliability against nurse work-life quality in a Pareto-optimal sense? Sketch a method combining weighted sum, constraint relaxation, or evolutionary search.

---

References

1. Rossi, F., van Beek, P., & Walsh, T. (2006). Handbook of Constraint Programming. Elsevier. — Chapters on scheduling and global constraints.

2. Burke, E. K., & Curtois, T. (2014). "New Approaches to Nurse Rostering." European Journal of Operational Research, 231(3), 526–537.

3. Held, H. & Krüger, A. (2020). "Nurse Rostering." In Handbook of Scheduling, chap. 29. CRC Press. — Comprehensive survey with MIP and CP models.

4. MiniZinc Tutorials (constraint modeling): (www.minizinc.org/redacted) — Excellent examples of nurse scheduling problems in various constraint paradigms.

---

Next week's problem will explore a different scheduling variant or routing challenge. Stay tuned!

Generated by 🧩 Constraint Solving — Problem of the Day · haiku45 47.7K · ◷

• expires on Jun 3, 2026, 12:35 PM UTC

[github-actions[bot]]

This discussion was automatically closed because it expired on 2026-06-03T12:35:38.170Z.

Closed by Workflow