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.
What is the run time complexity of integer linear programming (ILP)?
Asked Answered
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.
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.
From the last page of the paper that you link to: "Our result (Corollary 1) [...] is concerned with a fixed number of equalities." So, this paper is about equalities while the question seems to be about inequalities. –
Loriannlorianna
@UliSchlachter You're right. But, please notice that any inequality can be translated to equality with an extra variable. –
Turku
© 2022 - 2024 — McMap. All rights reserved.