Gilmore-Gomory列生成アルゴリズムの覚書
引用 ChatGPT
こちらの疑似コードは，Gilmore–Gomory 型の列生成アルゴリズムを「マスター問題（LP）」と「値付け問題（ナップサック）」の２層構造で表したものです。コメントを丁寧に入れているので，流れが追いやすいはずです。
//------------------------------
// 問題設定（例：切断在庫問題）
//------------------------------
// 入力：
// n ← 品目種類数
// b[i] ← 品目 i の需要本数, i=1…n
// L ← 原紙の長さ
// l[i] ← 品目 i の長さ
//
// 目的：必要な原紙本数を最小化
//------------------------------
//------------------------------
// 1. 初期パターンの生成
// （単位パターンなど，需給を満たすごくシンプルなパターン集合）
//------------------------------
P ← { for each i=1…n: pattern p that cuts one piece of type i }
// 各 pattern p はベクトル a[p][i] を持ち，
// a[p][i]＝そのパターンで何個の品目 i を切るか を表す
//------------------------------
// 2. 列生成ループ
//------------------------------
repeat
// 2.1 制限付きマスター問題（RMP: Restricted Master Problem）を解く
// decision var: x[p] ≥ 0 （パターン p を使う原紙枚数）
// minimize ∑_{p∈P} x[p]
// subject to ∑_{p∈P} a[p][i] * x[p] ≥ b[i] for all i=1…n
// x[p] ≥ 0
solve LP_RMP over P
let π[i] be dual variable for constraint i
// 2.2 値付け問題（Pricing Problem）を解く
// reduced cost = 1 - ∑_{i=1..n} π[i] * a_new[i]
// パターン a_new[・] をナップサックで探す：
// maximize ∑_{i=1..n} π[i] * y[i]
// subject to ∑_{i=1..n} l[i] * y[i] ≤ L
// y[i] ∈ ℤ_{\ge0}
// 目的関数最大値を V とすると，新列の reduced cost = 1 - V
solve knapsack with profits π[i], weights l[i], capacity L
obtain solution y[i] and objective V
if V ≤ 1 + ε then
// もはや「利益（π・y）」がコスト１を上回らない → 最適
break
end if
// 2.3 新しいパターン（列）を追加
let new pattern p' with a[p'][i] = y[i] for i=1…n
P ← P ∪ {p'}
until false
//------------------------------
// 3. 整数解への復元（必要なら）
//------------------------------
// RMP の解 x[p] は連続値なので，
// 整数計画法（Branch‑and‑Bound など）で
// x[p] ∈ ℤ_{≥0} 制約を加え再最適化する
solve IP over P if 整数解が必要
各ステップのポイント解説
-
初期パターンの準備
最初は「品目 i を１つだけ切るパターン」を入れておけば必ず実行可能。これでマスター問題（RMP）は常に解ける状態になります。 -
RMP を解いて双対値 π を得る
マスター問題は「今あるパターンを使って需要を満たすために最小何枚の原紙が必要か」を LP で解きます。ここで得られる双対値 π[i] は，「品目 i の需要を１増やすと目的関数がいくら増えるか」の“影響度”を示しています。 -
ナップサックで最有望パターンを探す
価格（利益）を π[i]，重さを l[i]，容量を原紙長 L とした整数ナップサック問題を解き，で得られる最大価値 V を用い，
が負（V > 1）なら「原紙１枚あたりに得られる“利得”がコスト１を上回る新パターンがある」＝追加すべき列がある、という判断になります。
-
終了判定
V が 1 以下（reduced cost ≥ 0）になったら，LP の下限としてもはや改善余地がないのでループを抜けます。 -
整数解
最終的に得られたパターン集合 P で，もし整数解（原紙枚数 x[p]∈ℤ）を求めたい場合は，この制限付きマスター問題を整数計画として再度解きます。
この流れにより，膨大な全パターンを最初から生成せず，必要なものだけ「列生成」で動的に加えていくことで，大規模問題を効率的に解けるのが Gilmore–Gomory の利点です。