16
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ "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. $\endgroup$
    – usul
    Feb 18, 2013 at 15:15
  • $\begingroup$ 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). $\endgroup$ Feb 18, 2013 at 18:55
  • 7
    $\begingroup$ @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$ $\endgroup$ Feb 18, 2013 at 23:15

2 Answers 2

22
$\begingroup$

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.

$\endgroup$
10
  • 1
    $\begingroup$ Ah, thanks for the term "fixed-parameter linear". That's what Lenstra's paper is about. See also: en.wikipedia.org/wiki/Parameterized_complexity $\endgroup$ Feb 18, 2013 at 19:02
  • 4
    $\begingroup$ just an obvious observation: for $n$ binary variables the bruteforce algorithms takes $O(n2^n m)$ time, so that case is trivial. $\endgroup$ Feb 18, 2013 at 20:17
  • $\begingroup$ 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/… . $\endgroup$ Feb 18, 2013 at 23:12
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 19, 2013 at 3:26
  • 2
    $\begingroup$ My paper is buggy for ILP: in base cases for "small" $m$, I referred to ILP algorithms for feasibility, when I should've referred to algorithms solving optimization. Eisenbrand's paper notes this and gives results for the base case; however, I couldn't figure out the exact dependence on $n$ in his paper. You could just plug the $O(n^{2.5n+o(n)} L)$ result into the $T(n,f(n),s)$ part of what I claimed, where $f(n)=4^n$, and so $L=4^n s$. (Sorry, I was confused about what $f(n)$ should be.) The upshot, ignoring that middle term, is something like $O(2^nnm+n^{2.5n+o(n)}(\log m) s)$ operations. $\endgroup$ Feb 20, 2013 at 20:27
5
$\begingroup$

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.

$\endgroup$

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.