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

 PSPとは？

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

zero-halfcutの具体例？

ゼロ・ハーフカットが「元の制約そのもの」にならない、ちゃんとした簡単例

ポイントは：

• 複数の制約を ½ 倍して足し合わせる

• その結果として 「元のどの制約とも違う、新しい不等式」が出てくる

• しかも 整数解は全部満たし、LP の分数解だけを締め出す

例えば、次の 3 つの制約を持つ 0–1 整数問題を考えます：

$$\begin{array}{rl}{\displaystyle x_1+x_2}& {\displaystyle \le 1}\\ {\displaystyle x_2+x_3}& {\displaystyle \le 1}\\ {\displaystyle x_1+x_3}& {\displaystyle \le 1}\\ {\displaystyle x_i}& {\displaystyle \in \{0,1\}}\end{array}$$

整数解は「高々1つだけ1になる」パターンだけですが、 LP 緩和では $x_1=x_2=x_3=0.5$ が許されてしまいます。

ここで 3 本の制約を全部 ½ 倍して足し合わせると：

$$\frac{1}{2}(x_1+x_2)+\frac{1}{2}(x_2+x_3)+\frac{1}{2}(x_1+x_3)\le \frac{1}{2}+\frac{1}{2}+\frac{1}{2}$$

左辺を整理すると：

$$x_1+x_2+x_3\le 1.5$$

右辺を整数に丸めると：

$$x_1+x_2+x_3\le 1$$

この不等式は：

• 元のどの制約とも違う「新しい」制約 （x₁+x₂≤1, x₂+x₃≤1, x₁+x₃≤1 のどれとも一致しない）

• 整数解はすべて満たす

• 分数解 (0.5,0.5,0.5) は 1.5 > 1 で 違反

これが、ちゃんとした意味での {0, ½}-cut の簡単な例です。

OK.その例だと、RMP世界だけで完結できるように思うが、どうしてPricerと関係があるのかを知りたい。

結論から言うと、 {0,½}-cuts は RMP の中だけで完結する「ただの強い制約」ではなく、 そのカットを RMP に追加した瞬間、PSP（Pricer）の構造が必ず変形する。 だから RMP と PSP は切り離せず、カットは必ず PSP に影響する。

あなたが感じた疑問は本質的で、列生成の理解の核心に触れています。 ここをクリアすると、CUT の意味が完全に腹落ちします。

🎯 なぜ「RMPだけで完結するように見える」のに PSP が関係するのか？

1. 列生成は「RMP＋PSPの二段構造」で動くから

RMP は「既存の列だけで最適化する」 PSP は「新しい列を作る（＝新しいスケジュールを生成する）」

カットを RMP に追加すると、 そのカットを満たす新しい列を PSP が生成できなければ意味がない。

つまり：

RMP にカットを追加した瞬間、PSP にもそのカットを反映しないと整合性が壊れる。

🎯 2. CUT は「列（スケジュール）に対する制約」だから

あなたの PDF（MDPI Systems 論文）では、CUT は次の形をしています：

$$\sum \lfloor \gamma a_{nl}\rfloor x_{nl}-\sum u_{dsk}\le \lfloor \gamma b\rfloor$$

ここで重要なのは xₙₗ（列変数）に係数が付くこと。

つまり CUT は：

• 列（スケジュール）に対する新しい制約

• その制約を満たす列しか RMP に入れられない

だから PSP は：

CUT を満たす列だけを生成するように、探索空間を制限しなければならない。

🎯 3. CUT を追加すると PSP に「新しいリソース」が追加される

論文の核心部分：

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

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

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

• rt の更新式は CUT の γ に依存する

• rt の上下限（drt_min, drt_max）が支配関係に入る

これが Pricerが重くなる理由であり、 非ロバストカットの本質です。

🎯 4. RMP だけで CUT を満たしても意味がない理由

もし RMP に CUT を追加しても、 PSP が CUT を無視して列を生成すると：

• PSP が「CUT を破る列」を生成する

• RMP に追加される

• RMP が CUT を満たさない列を採用してしまう

• RMP と PSP の整合性が崩壊する

だから CUT を追加した瞬間、 PSP にも CUT を反映する必要がある。

🎯 5. 列生成は「RMPの制約を PSP が守る」仕組みで動いている

列生成の本質はこれ：

RMP の制約を満たす列だけを PSP が生成するように、PSP に制約（リソース）を追加する。

CUT はまさにこの「PSP に追加される制約」そのもの。

🔥 まとめ（あなたの疑問への直接回答）

✔ {0,½}-cuts が RMP だけで完結しない理由

CUT は 列（スケジュール）に対する制約だから、 PSP が CUT を満たす列だけを生成するように PSP に新しいリソースを追加する必要がある。

✔ なぜ PSP が関係するのか

CUT を追加すると：

• PSP の DP に新しいリソース rt が追加される

• rt の更新式は CUT の γ に依存する

• 支配関係（dominance rule）が変わる

• 探索空間が変形する

• PSP の計算量が増える

つまり CUT は RMP と PSP の両方に影響する構造的な制約であり、 RMP だけで完結するものではない。