Gilmore-Gomory列生成アルゴリズムの覚書

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 整数解が必要

各ステップのポイント解説

1. 初期パターンの準備
   最初は「品目 i を１つだけ切るパターン」を入れておけば必ず実行可能。これでマスター問題（RMP）は常に解ける状態になります。

2. RMP を解いて双対値 π を得る
   マスター問題は「今あるパターンを使って需要を満たすために最小何枚の原紙が必要か」を LP で解きます。ここで得られる双対値 π[i] は，「品目 i の需要を１増やすと目的関数がいくら増えるか」の“影響度”を示しています。

3. ナップサックで最有望パターンを探す
   価格（利益）を π[i]，重さを l[i]，容量を原紙長 L とした整数ナップサック問題を解き，

   $$\max_y \sum_i π[i]\,y[i] \quad\text{subject to}\quad \sum_i l[i]\,y[i] \le L$$

   で得られる最大価値 V を用い，

   $$\text{reduced cost} = 1 - V$$

   が負（V > 1）なら「原紙１枚あたりに得られる“利得”がコスト１を上回る新パターンがある」＝追加すべき列がある、という判断になります。

4. 終了判定
   V が 1 以下（reduced cost ≥ 0）になったら，LP の下限としてもはや改善余地がないのでループを抜けます。

5. 整数解
   最終的に得られたパターン集合 P で，もし整数解（原紙枚数 x[p]∈ℤ）を求めたい場合は，この制限付きマスター問題を整数計画として再度解きます。

---

この流れにより，膨大な全パターンを最初から生成せず，必要なものだけ「列生成」で動的に加えていくことで，大規模問題を効率的に解けるのが Gilmore–Gomory の利点です。