列生成は、大規模な線形計画を効率的に解くための方法です。これは、すべての制約を 2 つのサブセットに分解する Dantzig と Wolfe の分解に基づいています。
中心となる考え方は、大規模な線形プログラムには変数 (または列) が多すぎて、それらすべてを明示的に表すことができないということです。最適な場合、ほとんどの変数は基準外であり、非常に多くの場合、それらのほとんどはゼロです。つまり、問題を解決するために考慮する必要があるのは変数の（小さな）サブセットだけです。
列生成を使用する方法では、小さな列のサブセットを使用して線形プログラムを初期化します。列を生成するメカニズムは、複数ステップのアルゴリズム内で、現在のソリューションを改善する可能性が高い変数、つまりコストがマイナスに削減される変数を生成することで構成されます。
この方法の有効性は、列の生成に使用されるメカニズムに大きく依存します。実際、解決すべき部分問題は NP 困難であることがよくあります。
列生成を使用するメソッドでは、双対問題の制約がメソッドの開始時に非常に不十分であるため、収束の問題がよく発生します。実際には、これらの問題により、メソッドは多数の反復を実行することになり、現在のソリューションを改善することができなくなります。
列を生成することで問題を効果的に処理
- 切断ストックの問題 (1 つまたは複数の寸法での切断)
- 車両ルートの問題
