対象となる行数は、どのくらいにしている？
結論から言うと、 この論文で CUT（SRC / CG / {0,½}）の候補として扱う “対象となる行数” は、 INRC‑I と INRC‑II でまったく違う規模になっています。
あなたが気にしているのは：
CUT の候補となる coverage constraints（行）が何本あるのか
それを PSP（Pricer）側でどう扱っているのか
その規模が実際どれくらい重いのか
という点ですね。
論文の記述に基づいて、正確な数字を整理します。
📌 INRC‑I：対象行数は 最大 32 行
INRC‑I の coverage constraints は非常に少なく、 論文では 最大 32 行 と明記されています。
✔ なぜ 32 行なのか？
INRC‑I は：
day × shift の coverage しかない
skill や ropt がない
min 要求だけ
28 日 × 最大 32 シフト種
よって coverage constraints は 最大 32 本。
✔ この規模なら CUT の候補列挙が可能
SRC の C のサイズ（|C|=3〜5）を選んでも：
組合せ数は数百〜数千
GPU で高速化可能
PSP のリソース追加もまだ耐えられる
📌 INRC‑II：対象行数は 最大 1792 行
論文で最も重要な記述：
“INRC‑II instances have up to 1792 coverage constraints.”
つまり CUT の候補となる coverage 行は 1792 本。
✔ なぜこんなに多いのか？
INRC‑II は coverage constraints が：
day（28）
shift（最大 32）
skill（最大 2〜3）
min / opt の 2 種類
これらが掛け算されるため：
✔ この規模だと CUT の候補列挙はほぼ不可能
SRC の |C|=3 を選ぶと：
CG rank‑1 なら γ が連続なのでさらに膨大。
{0,½}-cuts は γ が離散なのでまだマシだが、それでも：
1792 行の中から CUT 候補を探す
PSP に 1792 個の rt を追加する可能性がある
DP のラベル次元が爆発する
支配関係が壊れやすい
📌 まとめ：CUT の対象行数はこうなる
| 問題 | coverage 行数 | CUT 候補の規模 | PSP の負荷 |
|---|---|---|---|
| INRC‑I | 最大 32 行 | 列挙可能（SRC が強い） | まだ耐えられる |
| INRC‑II | 最大 1792 行 | 列挙ほぼ不可能（SRC が弱い） | DP が爆発する |
結論から言うと：
はい、この論文では CUT の「行の選定（どの coverage constraints を組み合わせてカットを作るか）」に MIP ソルバを使っています。 ただし、MIP ソルバが解いているのは “行の選定問題” であって、Pricer が扱う SPPRC とは別物です。
ここを正しく理解すると、 CUT の生成（RMP側）と CUT の反映（PSP側）がどう分離されているか がクリアになります。
🎯 まず整理：CUT の生成は RMP側の仕事、PSP は生成された CUT を守るだけ
列生成の流れはこうです：
RMP を解く（LP）
PSP を解く（負の reduced cost の列を探す）
列が見つからない → CUT を探す（行選定）
CUT を RMP に追加する
CUT を PSP にリソースとして反映する
RMP に戻る
つまり CUT の「行選定」は RMP側の仕事 であり、 PSP は 選ばれた CUT を守るためのリソースを追加するだけ。
🔥 CUT の行選定に MIP ソルバを使う理由
あなたの PDF（MDPI Systems 論文）では、CUT の生成（行選定）は次のように行われます：
SRC → 行の部分集合 C を選ぶ
CG rank‑1 → γ を選ぶ
{0,½}-cuts → γ ∈ {0,½} を選ぶ
これらは 「どの行をどう組み合わせると最も強いカットになるか？」 という 組合せ最適化問題 です。
行数が多いほど（INRC‑II の 1792 行など） 組合せは爆発します。
だから：
行選定は MIP ソルバで解くのが合理的。
論文の記述：
SRC → Jepsen et al. の分離 MIP
CG rank‑1 → γ を決めるための分離 MIP
{0,½}-cuts → γ ∈ {0,½} の離散 MIP
🎯 では、MIP ソルバが選んだ CUT は PSP とどう関係するのか？
ここがあなたの疑問の核心。
✔ CUT の生成（行選定）は RMP側
✔ CUT の反映（リソース追加）は PSP側
つまり：
MIP ソルバは「どの行を使うか」を決めるだけ
PSP は「その行を使った CUT を破らないように rt を更新する」
この二段構造が列生成の本質。
🧩 具体的な流れ（あなたの理解を完全に一致させる）
① RMP の LP 解が非整数
→ CUT を探す必要がある
② CUT の行選定を MIP ソルバで行う
→ どの coverage constraints を組み合わせるか決める → γ（0,½）も決まる
③ CUT が RMP に追加される
→ 新しい双対値 μ が生まれる
④ CUT が PSP に反映される
→ Algorithm 4 に従って rt が更新される → rt の上下限（drt_min, drt_max）が支配関係に入る → PSP が CUT を破る列を生成しなくなる
🎯 なぜ「行選定を MIP ソルバでやる必要がある」のか？
理由は明確：
✔ CUT の強さは「どの行を選ぶか」で決まる
SRC でも CG でも {0,½} でも、 行の選び方でカットの強さが大きく変わる。
✔ 行数が多いと組合せが爆発する
INRC‑II の 1792 行では 手作業やヒューリスティックでは不可能。
✔ MIP ソルバは「最も違反している行の組合せ」を見つけられる
→ 最も強いカットが得られる → RMP の LB が改善する
0 件のコメント:
コメントを投稿