Research Guide · Operations Research

Nurse Scheduling Integer Programming: A 4-Week ILP/MIP Guide

A practical walkthrough of how integer linear programming (ILP) and mixed-integer programming (MIP) formulations solve the nurse rostering problem — based on a 4-week model with 10+ operational constraints solved with the CBC solver in roughly 8 seconds across 35 parameter cases.

Why nurse scheduling is hard

Nurse scheduling is a classic NP-hard combinatorial optimization problem. A hospital must cover every shift, every day, with the right mix of skills — while honoring labor laws, contractual limits, fairness, and individual preferences. Manual schedules routinely violate constraints, create burnout, and push overtime spend up. Integer programming offers a provably feasible (and often optimal) schedule in seconds.

Decision variables

The core binary decision variable is:

x[n, d, s] ∈ {0, 1}

n ∈ N  : set of nurses (32 in the model: 24 FT, 8 PT, 4 charge)
d ∈ D  : set of days (28 — a 4-week horizon)
s ∈ S  : set of shifts (day, evening, night, off)

x[n, d, s] = 1 if nurse n works shift s on day d, else 0

Operational constraints

  1. Each nurse works exactly one shift per day (including off).
  2. Minimum staffing level per shift, per skill class.
  3. Maximum consecutive working days (typically 5–6).
  4. Minimum rest hours between shifts (no day→night turnarounds).
  5. Weekly hour caps for full-time and part-time contracts.
  6. At least one weekend off per 4-week cycle.
  7. Balanced night-shift distribution across the team.
  8. Charge-nurse coverage on every shift.
  9. Pre-approved time-off requests respected as hard constraints.
  10. Soft preference constraints penalized in the objective.

Objective function

The objective minimizes a weighted sum of overtime cost, unmet preferences, and schedule imbalance:

minimize  Σ (w₁ · overtime[n] +
           w₂ · unmet_preference[n] +
           w₃ · night_imbalance[n])

Solver setup

The model was implemented in Python with PuLP and solved with the open-source CBC (COIN-OR Branch-and-Cut) solver. Across 35 parameter cases — varying weights, demand profiles, and contract mixes — the model returned an optimal integer solution in roughly 8 seconds on a standard laptop. CBC's branch-and-bound with cuts was sufficient; no commercial solver (Gurobi, CPLEX) was needed.

Results and takeaways

  • 100% constraint satisfaction across all 35 cases.
  • ~12% reduction in projected overtime vs. the manual baseline.
  • Sensitivity analysis showed weight stability over a wide range.
  • Solve time of ~8s makes the model interactive for planners.

When to use ILP/MIP for scheduling

ILP/MIP shines when constraints are crisp, the planning horizon is short-to-medium, and the team values explainable, auditable schedules. For very large hospitals or rolling-horizon planning, consider column generation, Lagrangian relaxation, or metaheuristics (simulated annealing, tabu search) as complementary techniques.