Menu
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.
351
The simplex algorithm for linear programming has an exponential worst case time complexity, which we denote by O(2n), established by Klee and Minty [6] (also see Glossary entry). These are worst case values, so the actual time for a particular instance could be less.
Conclusion: ILP is NP-hard since 3-SAT is NP-complete.
Algorithms. The naive way to solve an ILP is to simply remove the constraint that x is integer, solve the corresponding LP (called the LP relaxation of the ILP), and then round the entries of the solution to the LP relaxation.
It is limited to continuous parameters with a linear relationship. This is the difference between linear programming (LP) and integer linear programming (ILP). In summary, LP solvers can only use real numbers and not integers as variables.
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.
152
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
