I'm wondering, what is the best known algorithm, in terms of Big-$O$ notation, to solve Integer Linear Programming?
I know that the problem is $NP$-complete, so I'm not expecting anything polynomial. And I know there are lots of heuristics and such that are used in practical applications like CPLEX, but I'm more interested in the formal, worst-case complexity of an exact algorithm.
Some $NP$-complete problems have algorithms in time $O(b^n p(n))$ where $1 < b < 2$ and $p$ is a polynomial. Vertex cover, independent set and 3SAT fall into this category, but general-SAT and TSP don't (as far as we know).
Can any such statements be made about Integer Programming, or particular sub-instances?
If anyone has a reference for the related problem of Quantifier Free Presburger Arithmetic, I'd be very interested in that too.
Asked By : jmite
Answered By : Juho
From what I can tell by searching, the definite survey seems to be:
In particular, Section 2.1 discusses integer programming in bounded dimension, and presents algorithms due to different authors. Indeed, the survey lists many references, and discusses some practical implementations.
For a fixed number of variables, integer linear programming is polynomial time solvable by Lenstra's algorithm.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/37550
0 comments:
Post a Comment
Let us know your responses and feedback