DISCRETE OPTIMIZATION & MILP LINEARIZATION NSP / NURSE SCHEDULING

Behind "Demon Castle 24-Hour Guard Shift" — Shift Scheduling (NSP) and Logical Linearization

TL;DR — A comprehensive guide to the mathematical optimization behind "Demon Castle 24-Hour Guard Shift." Learn how Nurse Scheduling Problems (NSP), sliding window consecutive limits, and partner synergy linearizations are formulated with Mixed-Integer Linear Programming (MILP) in WaSHI.

01Shift Scheduling (NSP) & Decision Variables

The Demon Castle Guard Roster must schedule guards for 5 weekdays across 3 shifts per day: Day (D), Evening (E), and Night (N). Mathematically, this is an instance of the Nurse Scheduling Problem (NSP), a classic combinatorial optimization challenge.

We define binary decision variable $x_{m,d,s} \in \{0, 1\}$ to indicate whether monster $m$ is assigned to day $d$ and shift $s$:

$$ x_{m,d,s} = \begin{cases} 1 & \text{if guard } m \text{ works on day } d \text{ during shift } s \\ 0 & \text{otherwise} \end{cases} $$

Each guard can work at most one shift per day (no overlapping shifts):

$$ \sum_{s \in \{\text{D, E, N}\}} x_{m,d,s} \le 1 \quad (\forall m, \forall d) $$

Every slot must meet its target headcount $R_{d,s}$:

$$ \sum_{m} x_{m,d,s} = R_{d,s} \quad (\forall d, \forall s) $$

02Consecutive Shift Limits & Sliding Window Formulation

To prevent guard exhaustion, maximum consecutive working days $L_m$ are enforced. Instead of tracking state variables or using non-linear branching, we formulate this using a Sliding Window over consecutive days:

$$ \sum_{k=0}^{L_m} \sum_{s} x_{m, d+k, s} \le L_m \quad (\forall m, \forall d \in \{1, \dots, D - L_m\}) $$

💡 Advantages of Sliding Window Formulation

This constraint uses only linear inequalities without introducing auxiliary state counters, resulting in tight LP relaxation bounds and fast MILP branch-and-bound convergence.

03Partner Synergy Linearization (McCormick Envelopes)

When two guards work the same shift, they may produce synergy bonuses (e.g. Goblin + Skeleton) or clash penalties. The interaction term is inherently non-linear ($x_A \cdot x_B$). In MILP, we introduce an auxiliary variable $\text{pair}_{A,B,d,s} \in [0, 1]$ and linearize it using McCormick envelopes:

$$ \begin{aligned} \text{(a)} \quad &\text{pair}_{A,B,d,s} \le x_{A,d,s} \\ \text{(b)} \quad &\text{pair}_{A,B,d,s} \le x_{B,d,s} \\ \text{(c)} \quad &\text{pair}_{A,B,d,s} \ge x_{A,d,s} + x_{B,d,s} - 1 \end{aligned} $$

💡 Simultaneous Handling of Positive & Negative Synergies

Upper bounds (a) and (b) prevent synergy bonuses when either guard is absent. Lower bound (c) enforces penalties when conflicting guards are scheduled together.

04Implementation with WaSHI

Here is how to express these constraints using @ohtaman/washi in TypeScript:

import { Model, expr, type Var } from "@ohtaman/washi";

const model = new Model("DemonCastleShift");

// 1. Binary shift assignment variables: x[guardId][day][shift]
const x: Record<string, Record<string, Record<string, Var>>> = {};
for (const m of guards) {
  x[m.id] = model.binary(days, shifts, { prefix: `x_${m.id}` });
}

// 2. Headcount requirement per shift
for (const d of days) {
  for (const s of shifts) {
    model.constraint(
      expr`sum(${guards}, ${(m: { id: string }) => x[m.id][d][s]}) == ${demand[d][s]}`
    );
  }
}

// 3. At most one shift per day
for (const m of guards) {
  for (const d of days) {
    model.constraint(expr`sum(${x[m.id][d]}) <= 1`);
  }
}

const status = await model.solve();
console.log("Status:", status);