algorithm - 二进制整数规划的单纯形算法的复杂性是多少？

Question

二进制整数规划问题的单纯形算法的复杂度是多少？对于最坏的情况或平均情况？

我正在解决分配问题。

参考：

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

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

Answer 1

由于它是针对分配问题的，因此变化很重要。在这种情况下，正如 wiki 页面所指出的，约束矩阵是完全单模的，这正是使您的问题也成为正常线性规划的实例所需要的（也就是说，您可以放弃完整性约束，结果将仍然是积分）。

因此，它可以在多项式时间内求解。然而，单纯形算法并不能保证这一点。

当然还有其他多项式时间算法来解决分配问题。

Answer 2

一般来说，二进制整数规划是 Karp 的 21 个 NP 完全问题之一，因此P!=NP可以肯定地说，Simplex 的最坏情况运行时间的下限为Ω(poly(n)). 同样，一般而言，与 SAT 求解器类似，“平均”情况将在很大程度上取决于您采用的平均值。在您获得有关您尝试使用单纯形法解决的问题类别的更具体信息之前，我认为没有一个好的答案。

当我有更多信息时，我会做更多的思考和更新。