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.