<p>The complexity of Lenstra's algorithm for mixed-integer programming in his paper runs as  <span class="math-container">$2^{O(n^3)}*poly(d, \phi)$</span>  where there are <span class="math-container">$n$</span> integer variables, <span class="math-container">$d$</span> continuos variables, and <span class="math-container">$\phi$</span> 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 <span class="math-container">$2^{O(n^3)}$</span>.  Certain improvements allow a Lentra-type algorithm to have a complexity of <span class="math-container">$2^{O(n \log(n))}$</span>.  Other techniques allow for even n^n in terms of the number of integer variables.</p>
<p>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.</p>

CC BY-SA 4.0
2016-10-07T19:22:25.333Z
2024-05-20T19:26:53.287Z
2024-05-20T19:26:53.287Z
Robert Hildebrand
<p>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?</p>

CC BY-SA 3.0
2014-09-12T14:44:03.780Z
Yes. Section 5 of Lenstra's original [paper](http://www.wisdom.weizmann.ac.il/mathusers/yaakovh/PKC2007/PrivatePapers/Lenstra81.pdf) covers this.
Austin Buchanan
CC BY-SA 3.0
2014-09-12T15:22:30.093Z
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?
Piotr Skowron
CC BY-SA 3.0
2014-09-12T15:29:39.053Z
I suggest that you look at the paper.
Austin Buchanan
<parameterized-complexity><integer-programming><fixed-parameter-tractable>
FPT algorithm for mixed integer program
Piotr Skowron
# FPT algorithm for mixed integer program

(Asked by: username_0 on 2014-09-12)

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?

**Tags:** parameterized-complexity, integer-programming, fixed-parameter-tractable

> **Comments:**
> **username_1**: Yes. Section 5 of Lenstra's original [paper](http://www.wisdom.weizmann.ac.il/mathusers/yaakovh/PKC2007/PrivatePapers/Lenstra81.pdf) covers this.  
> **username_0**: 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?  
> **username_1**: I suggest that you look at the paper.  

---

## 1 answers

### Answer by username_2 on 2016-10-07. Score: 6

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.


---

