FPT algorithm for mixed integer program

Question

It is known that every integer linear program parameterized by the number of variables is FPT (fixed parameter tractable). Is every mixed integer program parameterized by the number of integer variables also FPT?

• Austin Buchanan: Yes. Section 5 of Lenstra's original paper covers this.
• Piotr Skowron: Just to make sure: Lenstra's original paper does not use the term "FPT", but instead proves that there exists a polynomial algorithm if the number of variables is fixed. I understand that the fact that the problem is FPT is implicit in the paper (e.g., one can check that the complexity of the algorithm is, indeed, FPT). Is that right?
• Austin Buchanan: I suggest that you look at the paper.

Answer 1

The complexity of Lenstra's algorithm for mixed-integer programming in his paper runs as 2ドル^{O(n^3)}*poly(d, \phi)$ where there are $n$ integer variables, $d$ continuos variables, and $\phi$ is the binary encoding size of the problem. This is not stated very explicitly in his paper, but the main thing to notice is that the complexity is primarily guided by the number of subproblems, which is 2ドル^{O(n^3)}$. Certain improvements allow a Lentra-type algorithm to have a complexity of 2ドル^{O(n \log(n))}$. Other techniques allow for even n^n in terms of the number of integer variables.

Note that the method of Lenstra is easily applied to convex mixed integer optimization provided certain separation oracles exist. This dates back to a book of Gretchel, Lovasz, and Schrijver. Other results on semi-algebraic convex optimization exist for the pure integer case as an FPT.