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

 となると、RMP・Pricer共重たくなるのですね。

結論から言うと、 はい。CUT を入れると RMP も PSP（Pricer）も “両方” 重くなります。 しかも、これは避けられません。構造的に必然です。

ただし、 なぜ両方が重くなるのか、どちらがどれだけ重くなるのか、 そしてどうすれば重くなりすぎるのを防げるのか を理解すると、あなたのアルゴリズム設計（Max–Min除去、DUAL=0動的管理、低メモリラベル保存）に直結する重要な洞察になります。

ここでは あなたの PDF（MDPI Systems 論文）に基づいて、 RMP と PSP が “なぜ両方重くなるのか” を構造的に整理します。

🎯 1. CUT を入れると RMP が重くなる理由

RMP は「列（スケジュール）を並べて最適化する LP」です。

CUT を追加すると：

✔ RMP に新しい行制約が増える

• SRC → 数百〜数千の候補

• CG rank‑1 → γ が連続なので候補が膨大

• {0,½}-cuts → γ が離散なので比較的少ないが、それでも増える

✔ RMP の LP が大きくなる

• 行が増える

• 双対値 μ が増える

• LP の解く時間が増える

• 反復回数も増える

✔ RMP の双対値 μ が PSP のコストに入る

• μ が増えるほど PSP の reduced cost 計算が複雑化

• RMP と PSP の通信量も増える

🎯 2. CUT を入れると PSP（Pricer）が重くなる理由

あなたの PDFの最重要ポイント：

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

つまり CUT を追加すると PSP の DP（ラベル設定）に：

✔ 新しいリソース rt が追加される

• 連続勤務日数

• 休暇

• skill

• Max–Min

• DUAL=0

• そして CUT の rt（複数）

✔ ラベルの次元が増える

ラベルの次元が増えると：

• 支配関係が弱くなる

• ラベル数が爆発する

• DP が指数的に重くなる

• ZDD でも枝が増える

✔ rt の更新式は ceil（丸め）が入る

Algorithm 4：

$$rt\leftarrow rt+\sum \gamma -\lceil rt+\sum \gamma \rceil$$

• γ が ½ の場合、丸め誤差が蓄積

• rt の上下限（drt_min, drt_max）が複雑化

• 支配判定が壊れやすくなる

• DUAL=0 の扱いが難しくなる

🎯 3. なぜ「RMPだけ」でも「PSPだけ」でもダメなのか

あなたが鋭く指摘したように、

「PSP が CUT を守るなら、RMP に CUT を入れなくても良いのでは？」

これは列生成の本質的な疑問です。

答えは：

✔ PSP は「列の形」を守るだけ

✔ RMP は「列の価値」を決める

✔ CUT は「価値と形の両方」に影響する

✔ だから両方に入れないと整合性が壊れる

PSP が CUT を守っても、 RMP が CUT の双対値 μ を持っていなければ：

• PSP が CUT を破る列を「安い」と誤認する

• RMP がその列を採用してしまう

• 列生成が収束しない

🎯 4. 結果：CUT は RMP と PSP の両方を重くする

これは 非ロバストカットの宿命 です。

論文でも明記されています：

• SRC → PSP が重くなる

• CG rank‑1 → PSP がさらに重くなる

• {0,½}-cuts → PSP が比較的軽いが、それでも重くなる

• INRC‑II → 制約数が多すぎて PSP が爆発しやすい

Pricerは、一人のナースだけれども、複数のNurseについて計数する必要があるのでは？

結論から言うと：

Pricer（PSP）は “1人のナースのスケジュール” を生成するだけだが、 CUT の計数は “複数ナースの合計” を扱うため、 そのギャップを埋めるために Pricier にリソース（rt）を追加している。

つまり：

• RMP：複数ナースの合計で CUT を評価する世界

• PSP：1人のナースのスケジュールを作る世界

この「世界の違い」を一致させるために、 PSP に CUT のリソースを追加して、 “1人のナースが CUT にどれだけ寄与するか” を計数する必要がある。

ここが列生成の最も誤解されやすいポイントです。

🧩 なぜ「複数ナースの計数」を PSP が扱う必要があるのか？

■ RMP の CUT は “複数ナースの合計” に対する制約

例えば、{0,½}-cuts の一般形（あなたの PDFの式(10)）：

$$\sum _{n,l}\lfloor \gamma a_{nl}\rfloor x_{nl}-\sum _{dsk}{u}_{dsk}\le \lfloor \gamma b\rfloor$$

ここで左辺の第1項は：

• 複数ナース n の複数スケジュール l の合計

つまり CUT は 全ナースの合計で評価される制約。

■ しかし PSP は「1人のナースのスケジュール」しか扱わない

PSP が生成するのは：

• ナース n の

• 1つのスケジュール l

• そのスケジュールの reduced cost

つまり PSP は 1人分の列しか見ていない。

■ ではどうやって「複数ナースの合計」を扱うのか？

答えは：

PSP が生成する “1人のスケジュール” が CUT にどれだけ寄与するかを リソース rt として計数し、RMP の CUT と整合させる。

つまり：

• RMP は「複数ナースの合計」を見る

• PSP は「1人のナースの寄与」を見る

• その寄与を rt に蓄積することで、 PSP が CUT を破る列を生成しないようにする

🔥 具体的にどうやって「複数ナースの計数」を PSP が扱うのか？

あなたの PDFの Algorithm 4 が答えです。

PSP のラベル更新式：

$$rt\leftarrow rt+\sum {\gamma }_{dskm}-\lceil rt+\sum {\gamma }_{dskm}\rceil$$

ここで：

• γ は CUT の係数（0 or ½）

• γ は coverage 制約（複数ナースの合計）に由来する

• しかし PSP は「1人のナースのスケジュール」しか扱わない

だから：

PSP は “1人のナースが CUT にどれだけ寄与するか” を γ を使って計算し、rt に蓄積する。

この rt を RMP の CUT と整合させることで：

• PSP が CUT を破る列を生成しない

• RMP が CUT を満たす列だけを採用する

• 列生成が整合的に動く

🎯 なぜ「複数ナースの計数」を RMP だけでやってはダメなのか？

理由は明確：

✔ RMP が CUT を持っていても

✔ PSP が CUT を破る列を生成したら

✔ RMP がその列を採用してしまう

つまり：

PSP が CUT を守らないと、RMP の CUT は意味を失う。

だから CUT は：

• RMP にも入れる

• PSP にも入れる

という 二重構造が必須。