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?

  • 2
    $\begingroup$ Yes. Section 5 of Lenstra's original paper covers this. $\endgroup$ – Austin Buchanan Sep 12 '14 at 14:44
  • 1
    $\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 Skowron Sep 12 '14 at 15:22
  • $\begingroup$ I suggest that you look at the paper. $\endgroup$ – Austin Buchanan Sep 12 '14 at 15:29

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.