対象読者：混合整数線形計画（MIP）の基礎（二値変数・線形不等式・目的関数）をご存じの方。
現実の病院（ナース・スケジューリング）やコールセンター・警備現場で用いられるシフト最適化モデルが、ゲーム内の「夜勤明け日勤の禁止」「連勤上限」「ペア相性（二次項の線形化）」「単独夜勤の禁止」にどう1対1対応しているのかを解説します。
オペレーションズ・リサーチ（OR）の代表的な応用分野にナース・スケジューリング問題（Nurse Scheduling Problem; NSP）や人員配置問題（Staff Rostering）があります。『魔王城の24時間警備シフト』は、この古典的かつ実用的なMILPモデルをそのままファンタジー世界の拠点防衛パズルに翻案したものです。
| ゲームの要素 | 実務のシフト最適化での対応物 | 数理モデル上の表現 |
|---|---|---|
警備モンスター m ∈ M |
スタッフ・看護師・警備員 | 添字集合 M（各人のスキル・体力上限を持つ） |
日付 d ∈ D と昼番/夜番 s ∈ {day, night} |
計画期間の各日・各シフト区分 | 二値決定変数 x_{m,d,day}, x_{m,d,night} ∈ {0, 1} |
勇者軍の襲来戦力 R_{d,s} |
時間帯ごとの必要スキル量・需要予測 | 被覆制約（Covering Constraint）の右辺定数 |
| 夜番→翌日昼番の禁止 | 勤務間インターバル規制（夜勤明け日勤禁止） | 隣接シフト間の排他制約 x_{m,d,night} + x_{m,d+1,day} <= 1 |
| 連勤上限・週出勤上限・指定休 | 労働基準ルール・公休・希望休 | スライディング・ウィンドウ制約と変数固定 |
| プルルの「夜間単独配置の禁止」 | 新人スタッフの単独夜勤禁止（OJT同伴制約） | 含意制約（Implication Constraint） |
| 仲良しコンビ・不仲ペア | ペア配置推奨・同時配置回避 | 積 x_A * x_B の McCormick 線形化変数 p_{A,B,d,s} |
計画対象の日集合を D = {0, 1, …, T-1}、出撃可能な魔物の集合を M とします。各魔物 m ∈ M・各日 d ∈ D に対して、昼番に入るかどうかの二値変数 day_{m,d} ∈ {0, 1} と、夜番に入るかどうかの二値変数 night_{m,d} ∈ {0, 1} を定義します（両方 0 ならその日は「休み」です）。
たとえば「古竜ドラゴは最大 L_m = 1 連勤まで（＝1日働いたら翌日は必ず休み）」「ウェアウルフのフェンリルは最大 L_m = 3 連勤まで」といった連勤制限は、幅 L_m + 1 日のスライディング・ウィンドウを1日ずつずらしながら、「連続するどの L_m + 1 日間を切り取っても、その中の出勤日数は最大 L_m 日以下である（＝最低1日は休みがある）」と書けます。
L_m を漏れなく表現できます。しかもLP緩和が比較的タイトになるため、MILPソルバーの分枝限定法が高速に収束します。
ゲーム中盤から登場する新米スライムのプルルには、「夜番に入るときは1人きりにせず、必ず他の誰かと一緒に配置しなければならない」というルールがあります（実務のシフト表でも「新人看護師は夜勤に単独配置しない」という全く同じ制約が頻出します）。
論理式で書くと「もし night_{pururu, d} == 1 ならば、Σ_{m ≠ pururu} night_{m, d} >= 1」という含意（Implication）になりますが、二値変数の性質を使うと、たった1本の線形不等式に変換できます。
実際、他のメンバーが誰も夜番に入っていない（Σ_{m ≠ pururu} night_{m, d} == 0）ときは、night_{pururu, d} <= 0 となってプルルも配置できなくなり、逆に他の誰か1人でも夜番に入っていれば（和が 1 以上）、night_{pururu, d} <= 1 となってプルルも配置可能になります。
さらにゲーム性を深めているのが、メンバー間のペア相性（連携ボーナスと同番拒否）です。
Δ_{A,B} > 0）：同じシフト (d, s) に A と B の両方が入ると、連携ボーナスで防衛力と士気が +Δ_{A,B} 上がる。Δ_{A,B} < 0）：同じシフトに A と B が一緒に入ると、反発して防衛力と士気が Δ_{A,B} 下がる。
これを素直に式にすると、A の配置変数 x_{A,d,s} と B の配置変数 x_{B,d,s} の積（二次項）x_{A,d,s} * x_{B,d,s} が現れてしまい、そのままでは線形計画（MILP）になりません。
pair_{A,B,d,s} ∈ {0, 1} による標準線形化（Fortet / McCormick 線形化）
そこで、「A と B が同じ枠 (d, s) に同時配置されたときだけ 1 になる補助二値変数 pair_{A,B,d,s} ∈ {0, 1}」を導入し、次の3本の線形不等式で積 x_A * x_B と完全に等価にします。
Δ_{A,B} > 0）だけなら式(a)・(b)の上界だけでも目的関数が自然に pair = 1 を選びますが、負のペナルティ（Δ_{A,B} < 0、不仲ペア）がある場合はソルバーがペナルティを逃れようとして pair = 0 に下げようとします。そこに式(c)の下界 pair >= x_A + x_B - 1 があることで、「2人を同時に置いたら必ず pair = 1 になって減点を受ける」ことが厳密に強制されます。
各時間帯 (d, s) において、個人の実効防衛力 P_{m,s} とペア相性補正の合計が必要防衛力 R_{d,s} 以上になるよう被覆制約（Covering Constraint）を課し、全期間を通じた魔王城の総士気（Morale）を最大化します。
実務でもゲームでも、「条件を満たすシフト表を1つだけでなく、別のパターンも見てみたい」という場面があります。すでに得られた解の 1 の変数集合を S_1、0 の変数集合を S_0 としたとき、以下のNo-Good Cut（整数カット）を1本追加して再求解すると、直前のシフト表と最低1マス以上異なる次善解（または同点の別最適解）を瞬時に得ることができます。
// 直前のシフト割当と完全に同一の0-1パターンだけを禁止する No-Good Cut
// Σ_{v ∈ S_1} v - Σ_{u ∈ S_0} u <= |S_1| - 1
m.constraint(
expr`${sum(activeOnes)} - ${sum(activeZeros)} <= ${activeOnes.length - 1}`,
"forbid_exact_schedule"
);
Target Audience: Readers familiar with the basics of Mixed-Integer Linear Programming (binary variables, linear inequalities, and objective functions).
This article explains how real-world staff rostering and nurse scheduling models map directly onto the game's mechanics: rest intervals after night shifts, consecutive work limits, rookie supervision rules, and McCormick linearization of pairwise synergies and conflicts.
One of the most widely deployed applications of Operations Research (OR) is the Nurse Scheduling Problem (NSP) or Staff Rostering. "Demon Castle 24-Hour Guard Shift" adapts this practical MILP formulation into a fantasy castle defense puzzle.
| Game Element | Real-World Shift Scheduling Counterpart | Mathematical Model Representation |
|---|---|---|
Guard Monster m ∈ M |
Staff member, nurse, security guard | Index set M (each with skill levels and stamina caps) |
Day d ∈ D and Shift s ∈ {day, night} |
Planning horizon days and shift slots | Binary decision variables x_{m,d,day}, x_{m,d,night} ∈ {0, 1} |
Hero Army Raid Power R_{d,s} |
Required skill coverage / forecasted demand per slot | Right-hand side constant of the Covering Constraint |
| No Day Shift After a Night Shift | Minimum rest interval between shifts | Pairwise exclusion x_{m,d,night} + x_{m,d+1,day} <= 1 |
| Consecutive / Weekly Caps & Days Off | Labor regulations, weekly caps, requested PTO | Sliding-window constraints and variable fixing |
| Pururu's "No Solo Night Shift" | Junior staff supervision (no solo night duty) | Logical implication constraint |
| Synergy Pairs (+100) & Clashes (-150) | Preferred pairing / incompatible staff avoidance | McCormick linearization variable p_{A,B,d,s} for x_A * x_B |
Let D = {0, 1, …, T-1} denote the planning days and M denote the on-duty guard roster. For each guard m ∈ M and day d ∈ D, we define binary variables day_{m,d} ∈ {0, 1} and night_{m,d} ∈ {0, 1} (if both are 0, guard m rests on day d).
To enforce rules such as "Elder Dragon Drago can work at most L_m = 1 consecutive day (must rest the day after working)" or "Werewolf Fenrir can work at most L_m = 3 consecutive days," we slide a window of length L_m + 1 days across the horizon. Within every contiguous window of L_m + 1 days, the guard can work at most L_m days (guaranteeing at least one rest day inside the window):
L_m using pure linear inequalities without auxiliary state counters or non-linear branching. It also yields a tight LP relaxation, allowing branch-and-bound solvers to converge rapidly.
Rookie guards like Pururu the Slime have a supervision rule: "She cannot be assigned to a night shift alone; at least one other colleague must work the same night shift." (This mirrors hospital rostering rules where first-year nurses cannot staff a night ward solo.)
Logically, this is the implication night_{pururu, d} == 1 ⇒ Σ_{m ≠ pururu} night_{m, d} >= 1. Because all variables are binary, it translates into a single linear inequality:
When no other guard is assigned to night duty on day d (the sum is 0), the inequality forces night_{pururu, d} <= 0. As soon as at least one colleague is assigned (the sum is 1 or more), night_{pururu, d} <= 1 allows Pururu to join the shift.
Guard chemistry plays a central role in building a strong defense line:
Δ_{A,B} > 0): Assigning both A and B to the same slot (d, s) grants a +Δ_{A,B} (+100) teamwork bonus to defense power and morale.Δ_{A,B} < 0): Assigning both A and B to the same slot triggers a Δ_{A,B} (-150) conflict penalty.
Written directly, this introduces the quadratic product x_{A,d,s} * x_{B,d,s} of two binary variables, which is non-linear.
pair_{A,B,d,s} ∈ {0, 1} (Fortet / McCormick)
We introduce an auxiliary binary variable pair_{A,B,d,s} ∈ {0, 1} that equals 1 if and only if both A and B are assigned to slot (d, s), governed by three linear inequalities:
Δ_{A,B} > 0), upper bounds (a) and (b) alone would suffice because maximization naturally pushes pair up to 1. Conversely, for a negative conflict penalty (Δ_{A,B} < 0), the solver tries to set pair = 0 to dodge the penalty; inequality (c) provides the lower bound pair >= x_A + x_B - 1 that forces pair = 1 whenever both guards share a slot.
In each slot (d, s), the sum of individual effective defense powers P_{m,s} plus pairwise modifiers must cover the required power R_{d,s} and minimum headcount N_{d,s}, while maximizing total castle morale:
In both real-world scheduling and puzzle design, we often want to inspect alternative valid schedules. Given an existing binary solution with active ones S_1 and zeros S_0, adding a single No-Good Cut (Canonical Integer Cut) excludes that exact assignment pattern and finds the next-best (or tied optimal) schedule differing in at least one cell:
// No-Good Cut forbidding the exact previous 0-1 schedule assignment
// Σ_{v ∈ S_1} v - Σ_{u ∈ S_0} u <= |S_1| - 1
m.constraint(
expr`${sum(activeOnes)} - ${sum(activeZeros)} <= ${activeOnes.length - 1}`,
"forbid_exact_schedule"
);
适合读者：了解混合整数线性规划（MIP）基础（0-1变量、线性不等式与目标函数）的读者。
本文将解说现实医院（护士排班）、客服中心与安保现场使用的排班优化模型，是如何与游戏中的“禁止夜班次日早班”、“连续出勤上限”、“新人禁止单独夜班”以及“搭档相性（二次项线性化）”一一对应的。
运筹学（OR）中最具代表性的应用领域之一便是护士排班问题（Nurse Scheduling Problem; NSP）与人员排班问题（Staff Rostering）。《魔王城24小时警备排班》正是将这一经典且实用的 MILP 模型改编成了奇幻世界背景下的据点防卫益智游戏。
| 游戏要素 | 现实排班优化中的对应概念 | 数学模型中的表达方式 |
|---|---|---|
警备魔物 m ∈ M |
员工、护士、安保人员 | 指标集合 M（各自拥有不同技能与体力上限） |
日期 d ∈ D 与白班/夜班 s ∈ {day, night} |
计划周期内的各天与各班次 | 0-1 决策变量 x_{m,d,day}, x_{m,d,night} ∈ {0, 1} |
勇者军的进攻战力 R_{d,s} |
各时段所需技能总量与需求预测 | 覆盖约束（Covering Constraint）的右端常数 |
| 禁止夜班后次日紧接白班 | 班次间休息间隔规定（禁止夜班转早班） | 相邻班次互斥约束 x_{m,d,night} + x_{m,d+1,day} <= 1 |
| 连勤上限、周出勤上限与指定休假 | 劳动法规、公休与排休申请 | 滑动窗口（Sliding Window）约束与变量固定 |
| 普露露的“夜间禁止单人值班” | 新人禁止单独上夜班（带教同伴约束） | 逻辑蕴含约束（Implication Constraint） |
| 默契搭档（+100）与不睦组合（-150） | 推荐搭档组合与避免同班冲突 | 乘积项 x_A * x_B 的 McCormick 线性化辅助变量 p_{A,B,d,s} |
设计划周期的日期集合为 D = {0, 1, …, T-1}，可出勤的魔物集合为 M。对每位成员 m ∈ M 与每一天 d ∈ D，定义是否上白班的 0-1 变量 day_{m,d} ∈ {0, 1} 与是否上夜班的 0-1 变量 night_{m,d} ∈ {0, 1}（若两者均为 0，则当天为“休息”）。
例如“古龙德拉戈最多连续工作 L_m = 1 天（工作1天后次日必须休息）”、“狼人芬里尔最多连续工作 L_m = 3 天”这类限制，可以通过长度为 L_m + 1 天的滑动窗口（Sliding Window）逐日平移来表达：“在任意连续的 L_m + 1 天窗口内，出勤天数总和最多不超过 L_m 天（即窗口内至少有1天休息）”。
L_m，且具有较紧的 LP 松弛界，有助于分支定界求解器快速收敛。
游戏中期加入的新人史莱姆普露露有一条特殊规则：“安排夜班时不能让她独自一人，必须至少有一位其他同伴一起上夜班”（在医院排班中同样常见“新人护士不得单独值夜班”的带教约束）。
用逻辑式表示即蕴含关系：“若 night_{pururu, d} == 1，则 Σ_{m ≠ pururu} night_{m, d} >= 1”。利用 0-1 变量的性质，只需一条线性不等式即可完成转换：
当其他成员都没有安排当天夜班（求和为 0）时，不等式强制 night_{pururu, d} <= 0，普露露无法单独排入夜班；反之只要有任意一位前辈在夜班（求和 >= 1），night_{pururu, d} <= 1 即允许普露露一同出勤。
进一步丰富排班策略的是成员之间的搭档相性（协同加成与同班排斥）：
Δ_{A,B} > 0）：当 A 与 B 同时排入同一班次 (d, s) 时，触发协同加成，防卫力与士气提升 +Δ_{A,B}（+100）。Δ_{A,B} < 0）：当 A 与 B 被排入同一班次时，因互相排斥导致防卫力与士气下降 Δ_{A,B}（-150）。
若直接写出数学表达式，会出现两个 0-1 变量的乘积项（二次项）x_{A,d,s} * x_{B,d,s}，导致模型不再是线性规划。
pair_{A,B,d,s} ∈ {0, 1} 的标准线性化（Fortet / McCormick 线性化）
为此，我们引入辅助 0-1 变量 pair_{A,B,d,s} ∈ {0, 1}（仅当 A 与 B 同时排入班次 (d, s) 时取 1），并用以下3条线性不等式使其与乘积 x_A * x_B 完全等价：
Δ_{A,B} > 0），仅靠上界约束 (a)・(b)，最大化目标函数也会自动将 pair 推向 1；但当存在负惩罚（Δ_{A,B} < 0，不睦组合）时，求解器会试图将 pair 设为 0 来逃避扣分。此时下界约束 (c) pair >= x_A + x_B - 1 能够严格强制“只要两人同班，pair 就必须为 1 并扣除 150 点防卫力”。
在每个时段 (d, s)，个人实际防卫力 P_{m,s} 与搭档相性修正之和必须达到所需防卫力 R_{d,s} 及最低人数 N_{d,s}（覆盖约束），并在此基础上最大化全周期的总士气（Morale）：
无论在实际排班还是解谜中，我们常常希望看到不止一种可行排班方案。设已求得的某个解中取值为 1 的变量集合为 S_1，取值为 0 的变量集合为 S_0，只需向模型追加一条 No-Good Cut（整数割）并重新求解，即可排除刚才完全相同的排班表，立即求得至少有1格不同的另一组最优（或次优）排班方案：
// 仅禁止与上一组排班表完全相同的 0-1 组合的 No-Good Cut
// Σ_{v ∈ S_1} v - Σ_{u ∈ S_0} u <= |S_1| - 1
m.constraint(
expr`${sum(activeOnes)} - ${sum(activeZeros)} <= ${activeOnes.length - 1}`,
"forbid_exact_schedule"
);