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

[github-actions[bot]]

Problem Statement

Nurse Rostering is the scheduling problem of assigning nurses to shifts over a planning horizon while respecting labor regulations, staff preferences, and facility demand.

Concrete Instance

Consider a hospital ward with 4 nurses over a 7-day week. Each day requires:

• 1 nurse on day shift (08:00–16:00)
• 1 nurse on evening shift (16:00–00:00)
• 1 nurse on night shift (00:00–08:00)

Constraints:

• Each nurse works at most 2 shifts per day
• No nurse works more than 5 shifts per week
• Each nurse gets at least 2 consecutive days off per week
• Nurse A prefers no night shifts; Nurse B prefers weekends off

Goal: Find a valid roster that satisfies all hard constraints while minimizing violations of soft preferences.

Input/Output

Input:

• Set of nurses N, shifts S, planning period P (days)
• Demand d[s,p] = nurses needed for shift s on day p
• For each nurse: work limits, unavailability windows, preferences
• Penalty weights for soft constraints

Output:

• Assignment x[n,s,p] ∈ {0,1} = 1 if nurse n is assigned to shift s on day p
• Objective value: cost of constraint violations

---

Why It Matters

Healthcare operations: Hospital staffing is a critical operational challenge affecting patient safety and nurse burnout. Manual rostering is tedious and error-prone; automated solvers have reduced scheduling time from weeks to hours in major healthcare systems.

Staff satisfaction: Nurse scheduling directly impacts retention, morale, and work–life balance. Solvers that balance coverage and preferences significantly reduce turnover and help meet labor regulations (e.g., EU Working Time Directive).

Workforce management: Nurse rostering techniques extend to emergency dispatch, police patrols, airline crew scheduling, and call-center staffing—any domain with recurring shift-based demand.

---

Modeling Approaches

Approach 1: Constraint Programming (CP)

Paradigm: Declarative logic over discrete domains with sophisticated propagation

Model:

Variables:
  x[n,s,p] ∈ {0,1}    (nurse n assigned to shift s on day p)
  cost ∈ [0, M]       (weighted soft-constraint violations)

Hard constraints:
  ∀s,p: Σ_n x[n,s,p] = d[s,p]              (meet demand)
  ∀n,p: Σ_s x[n,s,p] ≤ 2                   (max shifts/day)
  ∀n: Σ_s,p x[n,s,p] ≤ 5                   (max shifts/week)
  ∀n: consecutive_off(x[n], 2, P)          (≥2 consecutive days off)
  ∀n,p: x[n, forbidden_shift[n], p] = 0    (unavailability)

Soft constraints (minimize):
  w_pref · Σ_n,p penalty[n,p] · x[n,s_pref_violate, p]
  w_balance · Σ_n |Σ_p x[n,s,p] - target_shifts[n]|

Minimize: cost

Strengths:

• Global constraints (e.g., cumulative, circuit, consecutive_off) provide strong propagation
• Natural expression of complex temporal and logical rules
• Efficient handling of availability windows and skill requirements

Weaknesses:

• Modeling soft preferences requires care (penalties, violation variables)
• Large instances (100+ nurses, months-long horizons) can overwhelm search

Solvers: OR-Tools CP-SAT, Gurobi CP, Chuffed

---

Approach 2: Mixed-Integer Programming (MIP)

Paradigm: Linear or quadratic objective + linear constraints over continuous and integer variables

Model:

Variables:
  x[n,s,p] ∈ {0,1}    (assignment)
  v[n] ∈ R_≥0         (preference violation cost for nurse n)
  z[n,d] ∈ {0,1}      (nurse n has day off on day d)

Hard constraints:
  ∀s,p: Σ_n x[n,s,p] = d[s,p]              (demand)
  ∀n,p: Σ_s x[n,s,p] ≤ 2                   (daily limit)
  ∀n: Σ_s,p x[n,s,p] ≤ 5                   (weekly limit)
  ∀n,p: Σ_s x[n,s,p] + z[n,p] ≥ 1 OR = 0  (off-days modeled via big-M)
  z[n,p] + z[n,p+1] ≥ 1                    (≥2 off-days via linear approximation)
  v[n] ≥ w · Σ_p x[n, unpreferred[n], p]   (preference violation lower bound)

Minimize: Σ_n v[n] + λ · Σ_n (Σ_p x[n,s,p] - target[n])2

Strengths:

• Powerful commercial solvers (CPLEX, Gurobi) with advanced presolve
• Scales well with fine-tuned LP relaxations
• Industry standard for production systems

Weaknesses:

• Consecutive-off constraints require big-M or auxiliary variables (adds variables/constraints)
• Quadratic objectives complicate some solvers; may require reformulation
• Less intuitive for modelers unfamiliar with linear algebra

Solvers: CPLEX, Gurobi, SCIP, CBC

---

Approach 3: Hybrid Local Search + Constraint Propagation

Paradigm: Start with a feasible greedy solution; iteratively improve via local moves (shift reassignments) guided by constraint violations

Sketch:

1. Greedy initialization: Assign nurses to shifts in demand order, satisfying hard constraints
2. Repeat until improving:
   • Pick a nurse and a shift; try reassigning
   • Evaluate change cost using constraint-satisfaction heuristic
   • Accept if improves objective or with Tabu/simulated annealing criterion
3. Use constraint propagation to prune infeasible neighbors

Strengths:

• Fast for large instances; finds good solutions quickly
• Easily embeds domain heuristics (e.g., "prefer senior nurses for critical shifts")
• Naturally handles complex, non-linear soft constraints

Weaknesses:

• No optimality guarantee; can get stuck in local optima
• Tuning search parameters requires problem knowledge
• Difficult to prove quality of solution

Solvers: Local search frameworks (e.g., OptaPlanner), custom imperative code

---

Key Techniques

1. Global Constraints & Propagation

The cumulative and element global constraints prune infeasible shift combinations early. The consecutive_off constraint efficiently enforces multi-day patterns without exponential auxiliary variables. Arc consistency (AC-3) on domain reductions tightens bounds before search.

2. Symmetry Breaking & Implied Constraints

Nurses are interchangeable—symmetry leads to redundant search. Add implied constraints like:

• Σ_p x[n,s,p] ≤ Σ_p x[n+1,s,p] (break nurse ordering symmetry)
• If two nurses have identical availability, order their assignments

These reduce the search tree exponentially for small instances.

3. Decomposition & Column Generation

Treat the problem as a set covering problem: enumerate feasible "blocks" (e.g., one nurse's complete weekly schedule), then select a minimum-cost subset covering all demand. Column generation iteratively adds promising blocks. This technique scales well and naturally incorporates preferences into block costs.

---

Challenge Corner

How would you model nurse rostering as a satisfiability problem (SAT)? SAT encodings typically scale worse than CP for scheduling, but they expose interesting structural insights. For instance:

• How many clauses do you need to express "nurse n works at most 2 shifts per day"?
• Can symmetry breaking via unit clauses help?
• What would a SAT solver's conflict analysis reveal about infeasible instances?

Bonus question: In a real hospital, demand fluctuates based on patient admissions. How would you extend the model to handle stochastic demand—e.g., day shifts might need 1–3 nurses with 60%, 30%, 10% probability? Would you use robust optimization, stochastic programming, or adaptive two-stage scheduling?

---

References

1. Rossi, F., van Beek, P., & Walsh, T. (Eds.). (2006). Handbook of Constraint Programming.
   Chapter 16 covers scheduling; excellent reference for global constraints and modeling patterns.

2. Brucker, P., Qu, R., & Burke, E. (2011). "Nurse scheduling." Handbook of Scheduling, 753–766.
   Survey of exact and heuristic approaches; practical case studies from European hospitals.

3. Gurobi & COIN-OR documentation: "Scheduling Problems."
   Free tutorials and example MIP models for nurse rostering and related problems.

4. Laborie, P., Rogerie, J., Shaw, P., & Vilím, P. (2018). "IBM ILOG CP Optimizer for scheduling." Constraints 23(2), 210–250.
   Detailed explanation of propagation algorithms and search strategies in industrial CP solvers.

Generated by 🧩 Constraint Solving — Problem of the Day · haiku45 · 6.42 AIC · ⌖ 4.07 AIC · ⊞ 5.8K · ◷

• expires on Aug 21, 2026, 3:42 AM UTC-08:00