整數線性規劃是否提供最佳解決方案？

我正在嘗試使用Integer線性編程（ILP）實現問題的解決方案。由於問題是NP難題，我想知道單純形法提供的解決方案是否最優？任何人都可以使用Simplex方法評論ILP的最優性或指向某些來源。有沒有其他算法可以提供ILP問題的最佳解決方案？整數線性規劃是否提供最佳解決方案？

編輯：我正在尋找的是/否回答任何的算法得到的溶液的最優（單純形法，分支定界和切割面）的ILP。

2013-03-08 Shan

具體。如果你問一個模糊的問題，你會得到一個模糊的答案。但是，如果您給我們詳細信息和背景，我們可以提供一個有用的答案。 – 2013-03-08 20:39:22

如果您的ILP是您的問題的正確表述，您將得到一個對應於您的優化約束的解決方案。假如你有足夠的耐心等待它，這可能需要很長時間。對於一個圖形佈局的np-hard問題，去年我使用了基於一般約束的編程;一天以上的圖表不超過50個頂點和250個邊緣。 – 2013-03-08 21:33:30

@羅伯特哈維全力以赴，問題不是模糊的。哈羅德有正確的答案。這個問題可能對於SO來說有點高級，與數學算法有關，而不是編程;但不需要上下文來理解所要求的內容。 – 2013-03-08 22:15:45

-2

根據定義，線性規劃問題的解決方案是最優的。

線性規劃是一類被稱爲「約束滿足」算法。一旦你滿足了你已經解決了這個問題的約束，並且沒有「更好的」解決方案，因爲根據定義，最好的結果是滿足約束條件。

如果你還沒有完全模擬的問題，但是，那麼很明顯，一些其他類型的解決方案可能會更好。

澄清：當我寫上面的「滿足約束條件」，我包括目標函數的最大化。切割平面算法實質上是單純形算法的擴展。

2013-03-08 21:39:15

感謝您的回答！ – Shan 2013-03-09 00:03:05

因爲這個答案是錯誤的而被Downvoted。在線性程序中，您正在尋找既滿足約束又優化（最小化或最大化）給定目標函數的解決方案。它也不回答什麼算法可以解決整數程序的問題。 – raoulcousins 2013-03-10 00:54:28

@raoulcousins爲什麼這個答案錯了？ – Shan 2013-03-11 10:00:20

單純形法不處理你想要的整數約束。簡單地舍入結果並不能保證提供最佳解決方案。

單純形法來解決的ILP問題，如果約束矩陣是totally dual integral確實工作。

解決ILP（不限於完全對偶積分約束矩陣）的一些算法是Branch and Bound，它易於實現，並且如果成本合理均勻一般效果良好（非常不均勻的成本使其嘗試多次嘗試一開始很有希望，但事實並非如此），並且Cutting Plane，我真的不太瞭解，但可能是很好的，因爲人們正在使用它。

2013-03-08 22:11:12 harold

回答