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

Question

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

标签： algorithmmatlabtime-complexitylinear-programming

Answer 1

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

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