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?
$\begingroup$
$\endgroup$
3
-
2$\begingroup$ Yes. Section 5 of Lenstra's original paper covers this. $\endgroup$– Austin BuchananCommented Sep 12, 2014 at 14:44
-
2$\begingroup$ 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? $\endgroup$– Piotr SkowronCommented Sep 12, 2014 at 15:22
-
$\begingroup$ I suggest that you look at the paper. $\endgroup$– Austin BuchananCommented Sep 12, 2014 at 15:29
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
