Chvátal–Gomory Cuts Applied to the Nurse Rostering Problemの論文その２

 CUTがViolateするとはどういうことですか？

結論： CUT（カット）が violate（違反）するとは、 「現在の RMP の LP 解が、そのカット不等式を満たしていない」 つまり 左辺 > 右辺 になってしまい、カットに“引っかかっている”状態 を意味します。

あなたの PDF（現在のタブ）にも明確に書かれています：

“the algorithm searches for violated cutting planes instead of terminating immediately”

🔍 CUT が violate するとは何か（本質）

カットは 整数解だけが満たす不等式 です。 しかし RMP は LP 緩和なので、非整数解が出ます。

その非整数解がカット不等式を満たさないとき：

$$\text{LHS}(x^{\ast })>\text{RHS}$$

この状態を “cut が violated” と呼びます。

📌 具体例（SRC の式で見る）

SRC の不等式（式 (8)）：

$$\sum \lfloor \gamma (\text{assignments})\rfloor x_{nl}-\sum udsk\le \lfloor \gamma (\text{requirements})\rfloor$$

RMP の解 $(x^{\ast },u^{\ast })$ を代入して、

$$\text{LHS}(x^{\ast },u^{\ast })>\text{RHS}$$

となれば violate。

つまり：

• LP 解が「本来あり得ないほど多くの assignment を同時に満たしている」

• LP 解が「丸め後の整数構造と矛盾している」

• LP 解が「整数 feasible set の外側にいる」

ということ。

🧠 なぜ violate を探すのか？

理由はシンプルで強力：

✔ violate しているカットを追加すると

その非整数解を禁止できる（排除できる） → RMP の feasible region が整数 hull に近づく → LB（下界）が上がる → PSP の dual が改善 → 探索効率が上がる

あなたの PDFにも：

“identify violated inequalities (cuts) … and add these cuts to exclude the non‑integer solution”

と書かれています。

📘 CUT が violate する状態を直感的に言うと

🔥「LP 解が嘘をついている」

整数世界では絶対に同時に成立しない組み合わせを LP が “0.3 + 0.3 + 0.4 = 1” のように 分数でごまかして満たしている。

SRC や CG カットはその “嘘” を暴く不等式です。

暴かれたら（violate したら） その嘘をつけないように RMP にカットを追加する。

🔚 まとめ

CUT が violate するとは：

• RMP の LP 解がカット不等式を満たしていない

• 整数 feasible set の外側にいる証拠

• その非整数解を排除するためにカットを追加できる状態

だから column generation は：

1. PSP で負の reduced cost が見つからない

2. → violate している CUT を探す

3. → 見つかったら RMP に追加

4. → LP 解を整数 hull に近づける

5. → LB が改善する

という流れになります。

PSPとは？

結論： あなたの読んでいる論文の文脈で PSP = Pricing Subproblem（価格付けサブ問題） の略です。 これは 列生成（Column Generation）における「新しい列（＝新しい看護師スケジュール）を作るための最重要パート」 です。 論文本文にも明確に書かれています。

🎯 PSPとは何か（あなたの論文の内容に完全準拠）

論文では、NRP（Nurse Rostering Problem）の列生成は次の2つで構成されます：

• RMP（Restricted Master Problem） → 既存のスケジュール列だけで最適化する線形緩和

• PSP（Pricing Subproblem） → 新しいスケジュール列を生成する問題 → 「負の reduced cost のスケジュール」を探す

論文の説明：

“The PSP generates individual schedules (columns) … with negative reduced costs.”

🧠 PSPの役割（列生成の心臓部）

PSPは 「看護師1人分のスケジュールを最適に作る」 問題です。

✔ PSPの目的

• RMPの双対値 λ を使って

• reduced cost が負になるスケジュール を探す

• 見つかれば RMP に追加して下界を改善する

論文の式 (7) が reduced cost の定義です。

🧩 PSPの正体：SPPRC（資源制約付き最短路問題）

論文では PSP を SPPRC（Shortest Path Problem with Resource Constraints） として解いています。

• グラフのノード：各日の勤務・休み状態

• パス：1人の看護師の28日間のスケジュール

• 資源：連続勤務日数、休暇、スキル、CUTによる追加リソースなど

• コスト：ペナルティ＋双対値による調整

論文の説明：

“The PSP for the NRP can be formulated as a shortest path problem with resource constraints (SPPRC).”

🔥 CUTを入れると PSP がどう変わるか？

あなたが今まさに読んでいる論文の核心部分です。

CUT（SRC / CG / {0,½}）を追加すると：

1. PSPに新しいリソース rt が追加される

2. ラベルの支配関係（dominance rule）が変わる

3. DPの計算量が増える（非ロバストカットの特徴）

論文の説明：

“each cut added to the master problem requires introducing a new resource in the pricing subproblem’s labeling algorithm.”

つまり、CUTを入れると PSP が重くなる。 これが「非ロバストカット」の意味です。

🧠 PSPが「価格付けサブ問題」と呼ばれる理由

列生成の一般理論では：

• RMPは「既存の列で最適化」

• PSPは「新しい列を作る」

• 新しい列の価値（reduced cost）を計算する → これが「pricing（価格付け）」と呼ばれる理由

NRPでは「列＝看護師のスケジュール」です。

🔚 まとめ

PSPとは：

• Pricing Subproblem（価格付けサブ問題）

• 列生成で新しいスケジュール列を作る部分

• SPPRCとしてDPで解く

• CUTを入れると新しいリソースが追加され、支配関係が変わる

• 列生成の下界改善の鍵となる