15
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Aardal, Karen, Robert Weismantel, and Laurence A. Wolsey. "Non-standard approaches to integer programming." Discrete Applied Mathematics 123.1 (2002): 5-74. gives a lot of references. Maybe you can find the answer by looking at these, or tracing what newer papers cite this one. Look at Section 2 in particular. $\endgroup$
    – Juho
    Apr 12, 2015 at 16:36
  • $\begingroup$ What's the difference between $O(1.1^{n})$ and $O(99^{n})$? $\endgroup$
    – greybeard
    Apr 13, 2015 at 7:33
  • $\begingroup$ @greybeard, not much for P vs NP, but a lot in terms of real life tractability, depending on the constants, it makes a huge difference. $\endgroup$ Apr 18, 2015 at 11:57
  • 1
    $\begingroup$ I wish I had been hoping for an up-front reminder that given $O(b^n)$ and $O(cn)$, a difference in $b$ results in a different set of functions, while one in $c$ doesn't and consequently gets abstracted away. $\endgroup$
    – greybeard
    Apr 18, 2015 at 15:50

1 Answer 1

4
+150
$\begingroup$

From what I can tell by searching, the definite survey seems to be:

Aardal, Karen, Robert Weismantel, and Laurence A. Wolsey. "Non-standard approaches to integer programming." Discrete Applied Mathematics 123.1 (2002): 5-74.

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.

$\endgroup$
2
  • $\begingroup$ fine, but what is the fastest known algorithm? $\endgroup$
    – vzn
    Apr 18, 2015 at 21:30
  • $\begingroup$ @vzn I don't know, this is at most an answer covering "particular sub-instances". $\endgroup$
    – Juho
    Apr 18, 2015 at 21:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.