列生成是精確還是啓發式算法？

我知道，列生成提供了一個最佳的解決方案，它可以與其他啓發式一起使用。但是，這是否使它成爲一個確切的算法？提前致謝。列生成是精確還是啓發式算法？

2017-04-20 Dipta

傳統的CG運作放鬆的問題。雖然它找到了最佳的LP解決方案，但這可能不會直接轉化爲最佳的MIP解決方案。對於某些問題（例如削減庫存），有證據表明這種差距很小，我們只是將用於放鬆問題的一組列列表應用於最終的MIP，因爲知道這是一個好的解決方案，但必然是最優的。所以這是一種啓發式。

通過一些努力，您可以在分支定界算法中使用列生成（這稱爲分支和定價）。這提供了久經考驗的最佳解

2017-04-20 09:43:10

回答