整数线性规划 (ILP) 的运行时间复杂度是多少？

Question

当有N个变量和R个约束时，整数线性规划(ILP) 问题的运行时间复杂度是多少？出于编码目的，我使用了 Matlab 的intlinprog函数。任何参考都会有所帮助。

Answer 1

如本链接所述，整数规划是 NP-Complete 。intlinprogMatlab中函数中使用的一些启发式方法（例如定义最小值和最大值以限制搜索空间），但它们根本无法改变问题的复杂性。

此外，如果所有值都在-ato之间a，我们有一个在 中运行的算法N^2(R*a^2)^{2R+3}。您可以在此处找到更多详细信息。