<p>No. The number of feasible solutions cannot be upper bounded by $f(k)n^{O(1)}$.</p>

<p>Consider the integer program
$I_n: 1 \le x\le 2^n$
with the integer variable $x$. So, $k=1$ and the program can be described with $O(n)$ bits. But it has $2^n$ solutions, which is exponential in the instance size.</p>

CC BY-SA 3.0
2013-03-22T22:07:52.247Z
2013-03-22T22:13:01.860Z
2013-03-22T22:13:01.860Z
Serge Gaspers
<p>It is well-known that Lenstra's famous algorithm (presented in the paper 
<em>Integer programming with a fixed number of variables</em>) can solve an ILP problem in $O^*(f(k))$ time where k is the number of variables occur in the ILP.</p>

<p>My question is that whether the algorithm or any of its improved versions can output all feasible solutions in $O^*(f(k))$ time?</p>

CC BY-SA 3.0
2013-03-22T18:16:32.260Z
What does $O^*$ mean?  See also [this answer](http://cstheory.stackexchange.com/a/16532/111) to a related question.
Jeffε
CC BY-SA 3.0
2013-03-22T22:10:10.960Z
The $O^*$ notation usually ignores polynomial factors in the instance size.
Serge Gaspers
<ds.algorithms><integer-programming>
Can Lenstra's algorithm output all feasible solutions in O^*(f(k)) time where k is the number of variables and f is a computable function in k?
Yang Yongjie
# Can Lenstra's algorithm output all feasible solutions in O^*(f(k)) time where k is the number of variables and f is a computable function in k?

(Asked by: username_0 on 2013-03-22)

It is well-known that Lenstra's famous algorithm (presented in the paper
*Integer programming with a fixed number of variables*) can solve an ILP problem in $O^\*(f(k))$ time where k is the number of variables occur in the ILP.

My question is that whether the algorithm or any of its improved versions can output all feasible solutions in $O^\*(f(k))$ time?

**Tags:** ds.algorithms, integer-programming

> **Comments:**
> **username_1**: What does $O^*$ mean?  See also [this answer](http://cstheory.stackexchange.com/a/16532/111) to a related question.  
> **username_2**: The $O^*$ notation usually ignores polynomial factors in the instance size.  

---

## 1 answers

### Answer by username_2 on 2013-03-22. Score: 7

No. The number of feasible solutions cannot be upper bounded by $f(k)n^{O(1)}$.

Consider the integer program
$I\_n: 1 \le x\le 2^n$
with the integer variable $x$. So, $k=1$ and the program can be described with $O(n)$ bits. But it has $2^n$ solutions, which is exponential in the instance size.


---

