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). 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$?
- 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)$.
- What is a good reference for this type of mixed integer linear program?