14
$\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$
  • 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 '15 at 16:36
  • $\begingroup$ What's the difference between $O(1.1^{n})$ and $O(99^{n})$? $\endgroup$ – greybeard Apr 13 '15 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$ – jmite Apr 18 '15 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 '15 at 15:50
  • $\begingroup$ @jmite Done. Was the reference of any use to you, or were you able to find some new information? $\endgroup$ – Juho Apr 18 '15 at 17:57
3
+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$
  • $\begingroup$ fine, but what is the fastest known algorithm? $\endgroup$ – vzn Apr 18 '15 at 21:30
  • $\begingroup$ @vzn I don't know, this is at most an answer covering "particular sub-instances". $\endgroup$ – Juho Apr 18 '15 at 21:40

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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