列生成

列生成または遅延列生成は、大規模な線形プログラムを解くための効率的なアルゴリズムです。

最も重要な考え方は、多くの線形プログラムが大きすぎてすべての変数を明示的に考慮することができないということです。 前提は、ほとんどの変数が非基本的であり、最適解ではゼロの値を仮定することです。 このため、問題を解決する際には、理論的には変数のサブセットのみを考慮する必要があります。 列生成は、このアイデアを活用して、目的関数を改善する可能性のある変数のみを生成し、つまり負のコストが低減された変数を見つける（一般性を損

解決される問題は、マスター問題とサブ問題の2つの問題に分かれています。 マスター問題は、変数のサブセットのみが考慮される元の問題です。 サブ問題は、新しい変数を識別するために作成された新しい問題です。 サブ問題の目的関数は、現在の双対変数に関する新しい変数のコストの削減であり、制約は変数が自然発生する制約に従うことを必要とします。

プロセスは次のように動作します。 マスター問題は解決されます—この解決策から、マスター問題の各制約に対して二重価格を得ることができます。 この情報は、サブ問題の目的関数に利用されます。 サブ問題は解決されます。 サブ問題の目的値が負の場合、負のコスト削減を持つ変数が特定されています。 その後、この変数がマスター問題に追加され、マスター問題が再解決されます。 マスター問題を再解決すると、新しい二重値のセットが生成され、負のコスト削減変数が特定されなくなるまでプロセスが繰り返されます。 サブ問題は負でないコストを削減した解を返し、マスター問題の解が最適であると結論付けることができます。

多くの場合、これにより、以前は難治性と考えられていた大規模な線形プログラムを解決することができます。 これがうまく使用される問題の古典的な例は、切断在庫問題です。 この種のアプローチを使用する線形計画法の特定の手法の1つは、Dantzig–Wolfe分解アルゴリズムです。 さらに，列生成は乗組員スケジューリング，車両ルーティング，容量化されたｐ-中央値問題などの多くの問題に適用されている。

この応用数学関連の記事はスタブです。 あなたはそれを拡大することによってWikipediaを助けることができます。