Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

The famous 1983 paper by H. Lenstra Integer Programming With A Fixed Number Of Variables states that integer programs with a fixed number of variables are solvable in time polynomial in the length of the data.

I interpret that as follows.

  1. Integer programming in general still is NP-complete but if my typical problem size at hand (say about 10.000 variables, an arbitrary number of constraints) is feasible in practice then I could construct an algorithm that scales polynomially in the number of constraints but not in the number of variables and constraints.
  2. The result is also applicable for binary programming since I can force any integer to 0-1 by adding an appropriate constraint.

Is my interpretation correct?

Does this result have any practical implications? That is, is there an implementation available or is it used in popular solvers like CPLEX, Gurobi, or Mosek?

Some quotes from the paper:

This length may, for our purposes, be defined to be n · m · log(a + 2), where a denotes the maximum of the absolute values of the coefficients of A and b. Indeed, no such polynomial algorithm is likely to exist, since the problem in question is NP-complete

[...]

It was conjectured [5], [10] that for any fixed value of n there exists a polynomial algorithm for the solution of the integer linear programming problem. In the present paper we prove this conjecture by exhibiting such an algorithm. The degree of the polynomial by which the running time of our algorithm can be bounded is an exponential function of n.

share|improve this question
1  
"I could construct an algorithm that scales polynomially in the number of constraints or variables but not in the number of variables and constraints." Interesting point/question -- so far we have seen this to be true for constraints (holding the number of variables fixed), but maybe it would be interesting to ask if it could true for variables (holding the number of constraints fixed) as well? Intuitively it feels like it should not be true, else IP would be polytime in general, but I'm not sure. –  usul Feb 18 '13 at 15:15
    
In section 4 of the paper Lenstra states that "the integer linear programming problem with a fixed value of m is polynomially solvable." (m is the number of contraints) This follows as a corollary of the main result. This section is not clear to me. On a second thought maybe he assumes fixed n AND m; meaning it is polynomial in "a" (the maximum of the absolute values of the coefficients of A and b). (I removed the "or variables" part from my question above as a consequence). –  Bernhard Kausler Feb 18 '13 at 18:55
4  
@usul: it is true and it does not imply that IP is polytime. it just means there is one algorithm that takes exponential time in $n$ and polynomial in $m$ and another that takes exponential time in $m$ and polynomial in $n$ –  Sasho Nikolov Feb 18 '13 at 23:15
    
@SashoNikolov Ah, great, thank you! –  usul Feb 19 '13 at 2:31
add comment

2 Answers

up vote 12 down vote accepted

The current fastest algorithm is actually linear in the length of the integer linear program for every fixed value of $n$. In his PhD thesis, Lokshtanov (2009) nicely summarizes the results by Lenstra (1983), Kannan (1987), and Frank & Tardos (1987) by the following theorem.

Integer Linear Programming can be solved using $O(n^{2.5n+o(n)} \cdot L)$ arithmetic operations and space polynomial in $L$. Here $L$ is the number of bits in the input and $n$ the number of variables in the integer linear program.

Thus, the problem is fixed-parameter linear parameterized by the number of variables.

1) Yes, Integer Linear Programming is "still" NP-complete. The running time of the theoretical result above depends only linearly on the number of constraints, so it scales nicely in the number of constraints. However I know of no actual implementation of this algorithm.

2) Yes, making the variables take binary values is straightforward as you observed.

Update. The dependence on $L$ can actually be improved in the running time for Integer Linear Programming. Based on Clarkson (1995) and Eisenbrand (2003) (see the comments below) one can obtain an algorithm with running time $$O(2^nnm + 8^n n \sqrt{m \log m} \log m + n^{2.5n+o(n)}s\log m)$$ where $m$ is the number of constraints and $s$ is the maximum number of bits required to encode a constraint or the objective function.

share|improve this answer
1  
Ah, thanks for the term "fixed-parameter linear". That's what Lenstra's paper is about. See also: en.wikipedia.org/wiki/Parameterized_complexity –  Bernhard Kausler Feb 18 '13 at 19:02
4  
just an obvious observation: for $n$ binary variables the bruteforce algorithms takes $O(n2^n m)$ time, so that case is trivial. –  Sasho Nikolov Feb 18 '13 at 20:17
    
For the optimization version of ILP: if it takes $T(n,m,s)$ time to solve a problem with rational coefficients and with $n$ variables, $m$ constraints, and $s$ bits per constraint, then ILP can be done in $O(2^n m + (\log m)T(n, f(n),s)$ operations on $O(s)$-bit rationals, where $f(n)$ is (I think) at worst $n^{O(n)}$; this is based on Eisenbrand's paper: www2.math.uni-paderborn.de/fileadmin/Mathematik/AG-Eisenbrand/… . –  Ken Clarkson Feb 18 '13 at 23:12
    
...sorry, make that $O(2^n n m+(\log m)T(n,f(n),s))$ expected (Las Vegas) time. –  Ken Clarkson Feb 18 '13 at 23:19
1  
This doesn't change the basic facts of your answer, but another relevant reference is K. L. Clarkson. Las Vegas algorithms for linear and integer programming when the dimension is small. J. ACM 42(2):488–499, 1995, doi:10.1145/201019.201036. –  David Eppstein Feb 19 '13 at 3:26
show 3 more comments

Here are a couple of points regarding the practical implications of Lenstra-type results, and possible implementations in CPLEX, Gurobi, etc. One of the key steps in most of such algos for IP is branching on "good" or "thin" directions, i.e., hyperplanes along which the width of the polytope is not too large (polynomial in variables and size of data). But Mahajan and Ralphs (preprint here) showed that the problem of selecting an optimal disjunction is NP-complete. So, it would appear hard to create practically efficient implementations of this class of algos.

Most of the algos implemented in packages such as CPLEX could be classified as branch-and-cut methods. This family of techniques typically work well on IP instances that are feasible, and are often able to find near-optimal solutions. But the focus of Lenstra-type algos are on worst case IP instances that are infeasible to start with, and the goal is to prove their integer infeasibility (and they study the complexity of this task). AFAIK, there are no class of problems with practical relevance that fit this description. So, CPLEX/Gurobi folks would probably not implement Lenstra-type algos any time soon.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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