列生成

列生成または遅延列生成は、大規模な線形計画問題を解くための効率的なアルゴリズムです。^{[ 1 ]}

基本的な考え方は、多くの線形計画問題は大きすぎて、すべての変数を明示的に考慮することができないという点です。そこで、まず対象となる計画問題を、変数のサブセットのみを使用して解くことから始めます。次に、目的関数を改善する可能性のある変数を、繰り返し計画問題に追加していきます。新しい変数を追加しても目的関数の値が改善されないことが証明できたら、この手順は終了します。列生成アルゴリズムを適用する際の期待は、ごくわずかな変数のみが生成されることにあります。この期待は、最適解ではほとんどの変数が非基底変数であり、値がゼロになるため、それらの変数なしで最適解を見つけることができるという事実によって裏付けられています。

多くの場合、この手法を用いることで、そうでなければ解決困難な大規模な線形計画問題を解くことが可能になります。この手法が効果的に用いられている典型的な例として、切断在庫問題が挙げられます。線形計画法においてこの種のアプローチを用いる手法の一つに、ダンツィヒ・ウォルフ分解アルゴリズムがあります。さらに、列生成法は、乗務員スケジューリング、車両経路決定、容量制約付きp-中央値問題など、多くの問題に適用されています。

このアルゴリズムは、主問題と副問題の2つの問題を考慮します。主問題とは、変数の一部のみを考慮した元の問題です。副問題とは、主問題の目的関数を改善できる変数（つまり、目的関数を改善できる変数）を特定するために新たに作成された問題です。

アルゴリズムはその後、以下のように進行する。

1. 主問題と副問題を初期化する
2. マスター問題を解く
3. 部分問題を用いて改善変数を探す
4. 改善変数が見つかった場合：それを主問題に追加してからステップ2に進みます。
5. それ以外の場合：主問題の解は最適解である。停止する。

この手順で最も難しいのは、マスター問題の目的関数を改善できる変数を見つけることです。これは、最も負の縮約コストを持つ変数を見つけることで可能です（一般性を失うことなく、問題が最小化問題であると仮定します）。負の縮約コストを持つ変数がない場合、マスター問題の現在の解は最適解となります。

変数の数が非常に多い場合、すべての縮約コストを計算して負の縮約コストを持つ変数を選択することで改善変数を見つけることは不可能です。そのため、縮約コストが最小となる変数のみを計算するという方法が考えられます。これは、元の問題の構造に大きく依存する価格設定部分問題と呼ばれる最適化問題を用いることで実現できます。部分問題の目的関数は、現在の双対変数に対する探索対象変数の縮約コストであり、制約条件は、変数が自然発生的な制約条件を満たすことを要求します。この構造によって部分問題を効率的なアルゴリズム（通常は専用の組み合わせアルゴリズム）で解くことが可能になる場合、列生成法は特に効率的です。

次に、変数の縮約費用を計算する方法と理由について詳しく説明します。標準形式の以下の線形計画問題を考えてみましょう。

${\displaystyle {\begin{aligned}&\min _{x}c^{T}x\\&{\text{制約条件}}\\&Ax=b\\&x\in \mathbb {R} ^{+}\end{aligned}}}$

これを主問題、およびその双対線形計画問題と呼ぶことにする。

${\displaystyle {\begin{aligned}&\max _{u}u^{T}b\\&{\text{条件}}\\&u^{T}A\leq c\\&u\in \mathbb {R} \end{aligned}}}$

さらに、${\displaystyle x^{*}}$そして$\displaystyle u^{*}}$これらは、任意の線形ソルバーによって提供される、これら 2 つの問題の最適解です。これらの解は、線形計画の制約を満たし、双対性により、目的関数 ( ) の値が同じになります。${\displaystyle c^{T}x^{*}=u^{*T}b}$) それを$\displaystyle z^{*}}$この最適値は、主問題のさまざまな係数の関数である。${\displaystyle z^{*}=z^{*}(c,A,b)}$双対変数が存在することに注意してください。$u_i*$主線形モデルの各制約に対して、最適な双対変数が$u_i*$最適値の偏微分として解釈できる$\displaystyle z^{*}}$係数に関する目的関数${\displaystyle b_{i}}$制約条件の右辺について：${\displaystyle u_{i}^{*}={\frac {\partial z^{*}}{\partial b_{i}}}}$またはその他${\displaystyle u^{*}={\frac {\partial z^{*}}{\partial b}}}$もっと簡単に言うと、$u_i*$係数が の場合に目的関数の最適値が局所的にどれだけ増加するかを示します${\displaystyle b_{i}}$1単位増加する。

ここで変数を考えてみましょう${\displaystyle y}$それまで主問題では考慮されていなかった。これは、変数が${\displaystyle y}$モデルには存在していたが、値はゼロだった。次に、の値を変更した場合の主問題への影響を観察する。${\displaystyle y}$から${\displaystyle 0}$に${\displaystyle {\hat {y}}}$。 もし${\displaystyle c_{y}}$そして${\displaystyle A_{y}}$はそれぞれ、変数に関連付けられた係数です。${\displaystyle y}$目的関数と制約条件が変更された場合、線形計画問題は次のように修正されます。

${\displaystyle {\begin{aligned}&\min _{x}c^{T}x+c_{y}{\hat {y}}\\&{\text{制約条件}}\\&Ax=b-A_{y}{\hat {y}}\\&x\in \mathbb {R} ^{+}\end{aligned}}}$

変数を追加することが興味深いかどうかを知るために${\displaystyle y}$問題に対して（つまり、ゼロ以外の値をとるように）、その値が${\displaystyle z_{\hat {y}}^{*}}$この新しい問題の目的関数の値は、${\displaystyle {\hat {y}}}$変数の${\displaystyle y}$増加します。言い換えれば、私たちは知りたいのです${\displaystyle {\frac {\partial z_{\hat {y}}^{*}}{\partial {\hat {y}}}}}$これを行うには、次の点に注意してください。${\displaystyle z_{\hat {y}}^{*}}$初期主問題の目的関数の値に応じて表現できる。${\displaystyle z_{\hat {y}}^{*}=c_{y}{\hat {y}}+z^{*}(c,A,b-A_{y}{\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 {\hat {y}}}$価値について${\displaystyle z_{\hat {y}}^{*}}$これは2つの用語に翻訳されます。まず、この変更は目的関数に直接影響を与え、次に、制約条件の右辺が変更され、それが最適変数に影響を与えます。${\displaystyle x^{*}}$その大きさは双対変数を用いて測定される$\displaystyle u^{*}}$導関数${\displaystyle {\frac {\partial z_{\hat {y}}^{*}}{\partial {\hat {y}}}}}$一般的には、変動費の削減コストと呼ばれます。${\displaystyle y}$そして、で表されます${\displaystyle cr_{y}}$以下に記載します。