列生成法のソースを表示

{{出典の明記|date=2024-05}}
'''列生成法'''（れつせいせいほう、{{Lang-en-short|Column generation}}）は大規模[[線形計画問題]]を効率的良く解く解法である。

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

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

== アルゴリズム ==
列生成法では主問題と部分問題からなる二つの問題について考える。主問題とは元の線形計画問題のことを指し、主問題から一部の変数のみを残した問題については限定主問題と呼ばれる{{Sfn|田中俊二|2017|p=970}}。一方、部分問題とは限定主問題の{{仮リンク|目的関数|en|objective function}}値を改善することができる新たな変数を求めるために解かれる問題である。

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

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

== 追加する変数を求める ==
列生成法において最も手間のかかる手続きは限定主問題の{{仮リンク|目的関数|en|objective function}}値を改善する新たな変数を求めることが挙げられる。この手続きで新たな変数を求める方法として各変数の目的関数の係数に対応する{{仮リンク|被約費用|en|reduced cost}}が負の中で最も小さいものを求めることが多い（ただし、最小化問題と仮定する{{Efn|線形計画問題は[[一般性を失わない|一般性を失う]]ことなく最小化問題として扱うことができる。}}。）。もし負の被約費用を持つ変数が存在しなければ、限定主問題の最適解は元の問題の最適性の条件を満たし、元の問題の最適解が求まったこととなる。

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

以下では変数の被約費用の求め方について述べる。ここでは標準形の線形計画問題について考える:
:<math> \begin{align}
&\min_{x}  c^T x  \\
&\text{subject to} \\
& A x = b \\
& x \in \mathbb{R}^+
\end{align} </math>
上記の定式化を主問題とし、以下に[[双対問題]]について記す:
:<math> \begin{align}
&\max_{u}  u^T b  \\
&\text{subject to} \\
& u^T A \leq c \\
& u \in \mathbb{R}
\end{align} </math>

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

主問題に新たな変数 <math>y</math> を追加する場合を考える。追加する変数は追加前の問題においてゼロの値をとっていたとみなすことができる。このとき、<math>y</math> を <math>0</math> から <math>\hat{y}</math> まで増加させる。<math>y</math> に対応する係数行列、ベクトルを <math>A_y</math>、<math>c_y</math> とすると問題は以下のように表される:

:<math> \begin{align}
&\min_{x}  c^T x + c_y \hat{y}  \\
&\text{subject to} \\
& A x = b - A_y \hat{y}\\
& x \in \mathbb{R}^+
\end{align} </math>

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

:<math> \begin{align}
\frac{\partial z_{\hat{y}}^*}{\partial \hat{y}} & ~=~ & & c_y + \frac{\partial z^*}{\partial \hat{y}} \\
& ~=~ & & c_y + \frac{\partial z^*}{\partial c} \frac{d c}{d \hat{y}} + \frac{\partial z^*}{\partial A} \frac{d A}{d \hat{y}} + \frac{\partial z^*}{\partial b} \frac{d b}{d \hat{y}} \\
& ~=~ & & c_y + \frac{\partial z^*}{\partial b} \frac{d b}{d \hat{y}} \\
& ~=~ & & c_y + u^* (-A_y) \\
& ~=~ & & c_y - u^* A_y
\end{align} </math>

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

== 脚注 ==
{{脚注ヘルプ}}
=== 注釈 ===
{{Notelist}}
=== 出典 ===
{{Reflist}}

== 参考文献 ==
* {{Cite journal |和書 |author=田中俊二 |year=2017 |title=大規模組合せ最適化問題に対する数理アプローチの基礎 |journal=計測と制御 |publisher=[[計測自動制御学会]] |volume=56 |issue=12 |pages=967-972 |ref=harv }}

== 関連項目 ==
* [[線形計画法]]
* [[ベンダーズ分解法]]
* [[切除平面法]]

== 外部リンク ==
* {{Cite web |url=https://www.msi.co.jp/solution/nuopt/docs/glossary/articles/ColumnGenerationMethod.html |title=列生成法 |publisher=[[NTTデータ数理システム]] |archive-url=https://web.archive.org/web/20241103222335/https://www.msi.co.jp/solution/nuopt/docs/glossary/articles/ColumnGenerationMethod.html |archive-date=2024-11-03 |accessdate=2025-03-05 }}

{{最適化アルゴリズム}}
{{Math-stub}}

{{DEFAULTSORT:れつせいせいほう}}
[[Category:最適化アルゴリズムとメソッド]]
[[Category:線型計画法]]
[[Category:数学に関する記事]]