列生成法

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

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

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

アルゴリズム

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

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

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

追加する変数を求める

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

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

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

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

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

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

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

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

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

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

{\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}}

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