问题描述
整数线性编程(ILP)问题的运行时复杂度是多少? N 个变量和 R 个约束条件是多少?为了进行编码，我使用了Matlab的 intlinprog 函数.任何参考都将有所帮助.
What is the run time complexity of integer linear programming (ILP) problem when, there are N number of variables and R number of constraints? For coding purpose I am using Matlab's intlinprog function. Any reference would be helpful.
推荐答案
整数编程是NP完成的，如此链接. Matlab intlinprog函数中使用的一些启发式方法(例如定义最小值和最大值以限制搜索空间)，但它们根本无法改变问题的复杂性.
Integer programming is NP-Complete as mentioned in this link. Some heuristic methods used in the intlinprog function in Matlab (such as defining min and max value to limit the search space), but they can't change the complexity of the problem at all.
此外，如果所有值都在-a到a之间，我们有一个在N^2(R*a^2)^{2R+3}中运行的算法.您可以在此处找到更多详细信息.
Also, if all values are between -a to a, we have an algorithm which runs in N^2(R*a^2)^{2R+3}. You can find more details here.
这篇关于整数线性规划(ILP)的运行时复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！