二进制整数规划的单纯形算法的复杂性是多少？
What is complexity of simplex algorithm for binary integer programming?
二进制整数规划问题的单纯形算法的复杂度是多少？对于最坏情况还是平均情况？
我正在解决 assignment problem。
参考文献：
在一般意义上，二进制整数规划是 Karp 的 21 个 NP 完全问题之一，因此假设 P!=NP 可以安全地说 Simplex 的最坏情况 运行 时间的下限为Ω(poly(n))。同样，一般来说，与 SAT 求解器类似，"average" 情况将在很大程度上取决于你所取的平均值。在您获得有关您尝试使用单纯形法解决的 class 问题的更多具体信息之前，我认为没有好的答案。
当我有更多信息时，我会做更多的思考和更新。
由于是分配问题，所以更改很重要。在那种情况下，正如 wiki 页面所指出的，约束矩阵是完全单模的，这正是使您的问题成为正常线性规划实例所需要的（也就是说，您可以删除完整性约束，结果将还是积分).
所以，它可以在多项式时间内解决。然而，Simplex 算法并不能保证这一点。
当然还有其他的多项式时间算法可以解决赋值问题
二进制整数规划问题的单纯形算法的复杂度是多少？对于最坏情况还是平均情况？
我正在解决 assignment problem。
参考文献：
在一般意义上，二进制整数规划是 Karp 的 21 个 NP 完全问题之一，因此假设 P!=NP 可以安全地说 Simplex 的最坏情况 运行 时间的下限为Ω(poly(n))。同样，一般来说，与 SAT 求解器类似，"average" 情况将在很大程度上取决于你所取的平均值。在您获得有关您尝试使用单纯形法解决的 class 问题的更多具体信息之前，我认为没有好的答案。
当我有更多信息时，我会做更多的思考和更新。
由于是分配问题，所以更改很重要。在那种情况下，正如 wiki 页面所指出的，约束矩阵是完全单模的，这正是使您的问题成为正常线性规划实例所需要的（也就是说，您可以删除完整性约束，结果将还是积分).
所以，它可以在多项式时间内解决。然而，Simplex 算法并不能保证这一点。
当然还有其他的多项式时间算法可以解决赋值问题