什麼是二元整數規劃的單純形算法的複雜性？

Question

什麼是二元整數規劃問題的單純形算法的複雜性？對於最壞的情況還是平均情況？我正在解決assignment problem。

參考文獻：

https://en.wikipedia.org/wiki/Integer_programming

https://en.wikipedia.org/wiki/Simplex_algorithm

Answer 1

在一般意義上，二進制整數規劃是卡普的21 NP完全問題之一，所以假設P!=NP它是安全地說，單純的最壞情況運行時間較低，範圍爲Ω(poly(n))。總體而言，與SAT解決方案類似，「平均」情況將嚴重依賴於您平均採用的平均值。除非你有更多具體的關於你試圖用simplex解決的問題的信息，否則我不認爲有一個好的答案。

我會做更多的思考和更新，當我有更多的信息。

Answer 2

由於它是用於分配問題，所以這一變化很重要。在這種情況下，正如維基頁面所指出的那樣，約束矩陣完全是單模態的，這也正是您需要將您的問題作爲正態線性編程實例的必要條件（也就是說，您可以放棄完整性約束，結果將會仍然是不可或缺的）。

因此，它可以在多項式時間內解決。然而，Simplex算法並不能保證。

當然，還有其他多項式時間算法來解決分配問題。