カラムの生成は正確なアルゴリズムかヒューリスティックなアルゴリズムですか？

Question

私は、列の生成が最適解を与え、他のヒューリスティックと併用できることを知っています。しかし、それは正確なアルゴリズムになりますか？前もって感謝します。

Answer 1

従来のCGは、リラックスした問題で動作します。最適なLPソリューションが見つかったにもかかわらず、これは最適なMIPソリューションに直接変換されない可能性があります。いくつかの問題（例えば、1dカットストック）については、このギャップが小さいという証拠があり、緩和された問題のために見つかったカラムのセットを最終的なMIPに適用するだけで、これは良い解決策であるが、それはヒューリスティックです。

いくつかの努力をして、ブランチアンドバインドアルゴリズム（これは分岐と価格と呼ばれます）内で列生成を使用できます。これにより、実証済みの最適解が得られます。