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.

Improve this question
$\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
    Commented Apr 12, 2015 at 16:36
  • $\begingroup$ What's the difference between $O(1.1^{n})$ and $O(99^{n})$? $\endgroup$
    – greybeard
    Commented 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$
    – Joey Eremondi
    Commented 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
    Commented Apr 18, 2015 at 15:50

1 Answer 1

Reset to default
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.

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.