Integer programming with a fixed number of variables 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.


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.
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.
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 &amp; 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.