<p>I studied Lenstra's paper <a href="https://www.jstor.org/stable/3689168" rel="noreferrer">https://www.jstor.org/stable/3689168</a>. I have no clue what complexity he provides on Mixed Integer Programming (it is too terse and it is not a stand alone paper as he assumes arguments of Khaichayan and Von zur Gathen and Sieveking). However I understand from the line '..we indicate an algorithm for the solution of this problem that is
 polynomial for any fixed value of $n$, the number of integer variables' that the complexity is polynomial if number of integer variables is fixed. I am interested in complexity with fixed number of integer variables and polynomial number of real variables.</p>

<p>Suppose we have $A\in\Bbb Z^{m\times(n_1+n_2)}$ and $B\in\Bbb Z^m$ and asked to find $X\in\Bbb Z^{n_1}\times \Bbb R^{n_2}$ in $AX\leq B$ then what is the complexity with with which we can find $X$?</p>

<ol>
<li>Can we find $X$ in $O(n_1^{cn_1}((n_2+1)m)^cL)$ arithmetic operations on $O(L^c)$ bit words where non-negative $c$ is fixed and $L$ is number of bits needed in any entry of $A$ or $B$?</li>
</ol>

<p>The above scaling is consistent with case $n_1=0$ (Real Linear Programming) or $n_2=0$ (Integer Linear Programming).</p>

<blockquote>
  <p>I am interested in case of $n_1$ is fixed and $n_2=O(L^c)$.</p>
</blockquote>

<ol start="2">
<li><p>Is there a down to earth explanation of what Lenstra is doing?</p></li>
<li><p>What is the space requirement?</p></li>
<li><p>What is a good reference for this type of mixed integer linear program?</p></li>
</ol>

CC BY-SA 3.0
2017-08-20T03:00:21.553Z
See this question: https://cstheory.stackexchange.com/questions/25747/fpt-algorithm-for-mixed-integer-program
Serge Gaspers
CC BY-SA 3.0
2017-08-20T03:13:04.663Z
@SergeGaspers would you know complexity? Lenstra squeezed any redundancy in that particular section.
Turbo
CC BY-SA 3.0
2017-08-20T12:27:24.220Z
The answer https://cstheory.stackexchange.com/a/36738/4896 discusses the complexity
Sasho Nikolov
CC BY-SA 3.0
2017-08-20T12:27:43.073Z
Possible duplicate of [FPT algorithm for mixed integer program](https://cstheory.stackexchange.com/questions/25747/fpt-algorithm-for-mixed-integer-program)
Sasho Nikolov
CC BY-SA 3.0
2017-08-20T12:29:18.130Z
@SashoNikolov no it is not.... I ask for exact complexity and there the query is if it really is FPT.... please read carefully... I am also asking for space requirement.
Turbo
CC BY-SA 3.0
2017-08-20T20:38:20.453Z
@SashoNikolov the first query in here implicitly asks whether is an improvement to Lenstra (look at scaling of terms).
Turbo
<cc.complexity-theory><ds.algorithms><reference-request><linear-programming><integer-programming>
What exactly did Lenstra prove on mixed integer linear program?
Turbo
# What exactly did Lenstra prove on mixed integer linear program?

(Asked by: username_0 on 2017-08-19)

I studied Lenstra's paper <https://www.jstor.org/stable/3689168>. I have no clue what complexity he provides on Mixed Integer Programming (it is too terse and it is not a stand alone paper as he assumes arguments of Khaichayan and Von zur Gathen and Sieveking). However I understand from the line '..we indicate an algorithm for the solution of this problem that is
polynomial for any fixed value of $n$, the number of integer variables' that the complexity is polynomial if number of integer variables is fixed. I am interested in complexity with fixed number of integer variables and polynomial number of real variables.

Suppose we have $A\in\Bbb Z^{m\times(n\_1+n\_2)}$ and $B\in\Bbb Z^m$ and asked to find $X\in\Bbb Z^{n\_1}\times \Bbb R^{n\_2}$ in $AX\leq B$ then what is the complexity with with which we can find $X$?

1. Can we find $X$ in $O(n\_1^{cn\_1}((n\_2+1)m)^cL)$ arithmetic operations on $O(L^c)$ bit words where non-negative $c$ is fixed and $L$ is number of bits needed in any entry of $A$ or $B$?

The above scaling is consistent with case $n\_1=0$ (Real Linear Programming) or $n\_2=0$ (Integer Linear Programming).

> I am interested in case of $n\_1$ is fixed and $n\_2=O(L^c)$.

2. Is there a down to earth explanation of what Lenstra is doing?
3. What is the space requirement?
4. What is a good reference for this type of mixed integer linear program?

**Tags:** cc.complexity-theory, ds.algorithms, reference-request, linear-programming, integer-programming
> **Comments:**
> **username_1**: See this question: https://cstheory.stackexchange.com/questions/25747/fpt-algorithm-for-mixed-integer-program  
> **username_0**: @SergeGaspers would you know complexity? Lenstra squeezed any redundancy in that particular section.  
> **username_2**: The answer https://cstheory.stackexchange.com/a/36738/4896 discusses the complexity  
> **username_2**: Possible duplicate of [FPT algorithm for mixed integer program](https://cstheory.stackexchange.com/questions/25747/fpt-algorithm-for-mixed-integer-program)  
> **username_0**: @SashoNikolov no it is not.... I ask for exact complexity and there the query is if it really is FPT.... please read carefully... I am also asking for space requirement.  
> **username_0**: @SashoNikolov the first query in here implicitly asks whether is an improvement to Lenstra (look at scaling of terms).  

---

## 0 answers

