列生成法

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。 出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "列生成法" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL (2024年5月)

列生成法（れつせいせいほう、英: Column generation）は大規模線形計画問題を効率的良く解く解法である。

列生成法が用いられる背景として多くの実用上の線形計画問題は大規模な問題であり、変数の数が非常に多いことから、これらの変数から組み合わされる基底解を生成して最適解を求めるという手続きが現実的でないことが挙げられる。このことから、列生成法では所与の線形計画問題から一部分の変数のみからなる問題について考え、これを解いて目的関数値を改善することができる変数を逐次追加していくアルゴリズムである。ある時点で目的関数を改善できるような変数が見つからなくなった時点で列生成法は終了する。列生成法を適用することで考えられる利点として、解の生成が少ない段階で最適解が求まり早期に終了することが挙げられる。実際、線形計画問題では最適解において変数の値がゼロとなる非基底解となる変数が非常に多いことがあるため、非基底変数について考慮せず少数の変数のみゼロでない値、基底解となることを考慮し、最適解を求めることが期待できる。

ほとんどの場合において列生成法は大規模な線形計画問題に対して効果的な解法となる。古くから効果的な例として知られている問題は板取り問題が挙げられる。またダンツィーグ・ウルフ分解は線形計画問題に列生成法を適用する際に度々用いられる技法となっている。他に列生成法が適用される問題として、乗務員スケジューリング問題（英語版）、配送計画問題、容量制約付きpメディアン問題などが知られている。

列生成法では主問題と部分問題からなる二つの問題について考える。主問題とは元の線形計画問題のことを指し、主問題から一部の変数のみを残した問題については限定主問題と呼ばれる^[1]。一方、部分問題とは限定主問題の目的関数値を改善することができる新たな変数を求めるために解かれる問題である。

列生成法は以下の手続きによって構成されている:

1. （限定）主問題と部分問題を初期化する。
2. （限定）主問題を解く。
3. 部分問題を解いて（限定）主問題を改善するような新たな変数を求める。
4. もし新たな変数が見つかれば、（限定）主問題に新たな変数を加えてステップ2へ戻る。
5. そうでなければ、（限定）主問題を解いて求まった最適解が主問題（元の問題）の最適解として列生成法は終了する。

列生成法において最も手間のかかる手続きは限定主問題の目的関数値を改善する新たな変数を求めることが挙げられる。この手続きで新たな変数を求める方法として各変数の目的関数の係数に対応する被約費用（英語版）が負の中で最も小さいものを求めることが多い（ただし、最小化問題と仮定する^{[注釈 1]}。）。もし負の被約費用を持つ変数が存在しなければ、限定主問題の最適解は元の問題の最適性の条件を満たし、元の問題の最適解が求まったこととなる。

しかしながら、元の問題の変数が非常に多い場合にはすべての被約費用について調べることは効率が悪い。そのため、被約費用が最も小さい変数についてのみ調べて、被約費用が正負について調べれば元の問題の最適解であるかを判定することができる。被約費用の最も小さい変数を調べる方法として価格付け問題を解くことで実現できる。なお価格付け問題は元の問題の構造に依存して構成される問題であり、価格付け問題の解きやすさは問題によって異なっており、価格付け問題が容易に解ける問題に対しては列生成法が効果的な解法となることがある。限定主問題の目的関数値の改善を判定するため部分問題の目的関数は限定主問題に含まれていない変数の被約費用、すなわち双対変数に対応している。また制約条件は主問題の制約条件と同一である。問題の構造を利用した組合せアルゴリズムによって部分問題を容易に解くことで列生成法は効率よく動作することができる。

以下では変数の被約費用の求め方について述べる。ここでは標準形の線形計画問題について考える:

${\displaystyle \min }$		${\displaystyle c^{\top }x}$
${\displaystyle \mathrm {s.t.} }$		${\displaystyle Ax=b}$
		${\displaystyle x\in \mathbb {R} ^{+}}$

上記の定式化を主問題とし、以下に双対問題について記す:

${\displaystyle \max }$		${\displaystyle u^{\top }b}$
${\displaystyle \mathrm {s.t.} }$		${\displaystyle u^{\top }A\leq c}$
		${\displaystyle u\in \mathbb {R} }$

加えて、主問題の最適解を${\displaystyle x^{*}}$、双対問題の最適解を ${\displaystyle u^{*}}$ とする。これらの最適解はそれぞれの制約条件を満たしつつ、それらの最適値 ${\displaystyle z^{*}}$ は一致することが知られている（すなわち、${\displaystyle c^{T}x^{*}=u^{*T}b}$）。また双対変数 ${\displaystyle u_{i}^{*}}$ は主問題の各制約に対応している。これらのことから、双対変数 ${\displaystyle u_{i}^{*}}$ は主問題の制約の右辺の定数 ${\displaystyle b_{i}}$ に対応する目的関数 ${\displaystyle z^{*}}$ の微分係数 ${\displaystyle u_{i}^{*}={\frac {\partial z^{*}}{\partial b_{i}}}}$ すなわち ${\displaystyle u^{*}={\frac {\partial z^{*}}{\partial b}}}$ と解釈することができる。端的に言えば、${\displaystyle u_{i}^{*}}$ は目的関数を単位増加量あたり ${\displaystyle b_{i}}$ 増やすことができるかを表す。

主問題に新たな変数 ${\displaystyle y}$ を追加することを考える。追加する変数は追加前の問題において値はゼロに固定されたものとみなすことができる。続いて、${\displaystyle y}$ を ${\displaystyle 0}$ から ${\displaystyle {\hat {y}}}$ まで増加させる。${\displaystyle y}$ に対応する係数行列、ベクトルをそれぞれ ${\displaystyle A_{y}}$、${\displaystyle c_{y}}$ とすると問題は以下のように表される:

${\displaystyle \min }$		${\displaystyle c^{\top }x+c_{y}{\hat {y}}}$
${\displaystyle \mathrm {s.t.} }$		${\displaystyle Ax=b-A_{y}{\hat {y}}}$
		${\displaystyle x\in \mathbb {R} ^{+}}$

今、変数 ${\displaystyle y}$ を追加した問題が ${\displaystyle y}$ の値を増加させることによって ${\displaystyle {\hat {y}}}$ が減少し、結果としてその問題の最適値 ${\displaystyle z_{\hat {y}}^{*}}$ をより良くするような変数 ${\displaystyle y}$（元の問題の最適解においてゼロの値をとらない変数）について求めることを考える。つまり、${\displaystyle {\frac {\partial z_{\hat {y}}^{*}}{\partial {\hat {y}}}}}$ について求める必要がある。${\displaystyle {\frac {\partial z_{\hat {y}}^{*}}{\partial {\hat {y}}}}}$ は以下のようにして求められる:

${\displaystyle {\begin{aligned}{\frac {\partial z_{\hat {y}}^{*}}{\partial {\hat {y}}}}&~=~&&c_{y}+{\frac {\partial z^{*}}{\partial {\hat {y}}}}\\&~=~&&c_{y}+{\frac {\partial z^{*}}{\partial c}}{\frac {dc}{d{\hat {y}}}}+{\frac {\partial z^{*}}{\partial A}}{\frac {dA}{d{\hat {y}}}}+{\frac {\partial z^{*}}{\partial b}}{\frac {db}{d{\hat {y}}}}\\&~=~&&c_{y}+{\frac {\partial z^{*}}{\partial b}}{\frac {db}{d{\hat {y}}}}\\&~=~&&c_{y}+u^{*}(-A_{y})\\&~=~&&c_{y}-u^{*}A_{y}\end{aligned}}}$

新たな問題の目的関数値を ${\displaystyle z_{\hat {y}}^{*}}$ とする。言い換えると、${\displaystyle z_{\hat {y}}^{*}}$ の ${\displaystyle {\hat {y}}}$ を変動させると、目的関数と制約条件の右辺に影響を及ぼし、やがて ${\displaystyle u^{*}}$ が変化することで最適解 ${\displaystyle x^{*}}$ も変動する。微分係数 ${\displaystyle {\frac {\partial z_{\hat {y}}^{*}}{\partial {\hat {y}}}}}$ は ${\displaystyle y}$ の被約費用を表し、${\displaystyle cr_{y}}$ と表される。

• 田中俊二「大規模組合せ最適化問題に対する数理アプローチの基礎」『計測と制御』第56巻第12号、計測自動制御学会、2017年、967-972頁、CRID 1390282681525368320、doi:10.11499/sicejl.56.967、ISSN 18838170、NAID 130006250916、NCID AN00072406、2025年5月13日閲覧。 

• 線形計画法
• ベンダーズ分解法
• 切除平面法
• ダンツィーグ・ウルフ分解法

• “列生成法”. NTTデータ数理システム. 2024年11月3日時点のオリジナルよりアーカイブ。2025年3月5日閲覧。

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形（無制約）	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 放物線補間 パウエル法 勾配法 収束性 信頼領域 ウルフ条件 準ニュートン法 BFGS法 ブロイデン法 L-BFGS法 DFP法 SR1法 BHHH法 その他の求解法 ガウス・ニュートン法 最急降下法（確率的） レーベンバーグ・マーカート法 共役勾配法（非線形共役勾配法） 打ち切りニュートン法 ドッグレッグ法 鏡像 座標 バルジライ・ボールウェイン法 … ヘッセ行列 最適化におけるニュートン法
非線形（制約付き）	一般 バリア関数 ペナルティ関数法 微分可能 ラグランジュの未定乗数法 拡張ラグランジュ関数法 逐次二次計画法 逐次線形計画法 逐次線形二次計画法
凸最適化	凸最小化 切除平面法 簡約勾配法 劣勾配法 近接勾配法 線形 および 二次 内点法 アフィンスケーリング法 カーマーカーの射影変換法 メロートラの予測子修正子法 基底-交換 単体法 改訂単体法 十文字法 レムケの相補掃き出し法 その他 カチヤンの楕円体法 有効制約法 列生成法 ベンダーズ分解法
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題（分枝限定法・分枝カット法・分枝価格法） グラフ理論 最小全域木 ブルーフカ法 クラスカル法 プリム法 最短経路問題 ベルマン–フォード法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法 ネットワークフロー (最大流問題) ディニッツ法 エドモンズ・カープ法 フォード・ファルカーソン法 プリフロープッシュ法
メタヒューリスティクス	進化的アルゴリズム（進化戦略・遺伝的アルゴリズム） 山登り法 局所探索法 焼きなまし法 タブーサーチ 群知能 ベイスンホッピング法 量子焼きなまし法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア

この項目は、数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。

• 表示
• 編集