Say we're given a parallelepiped defined by the vectors $\mathbf{x}_1,\dots,\mathbf{x}_k$ with integer entries. Is there any way to quickly determine whether it strictly contains an integer vector and if so find it?
One could of course brute force this, but if the vectors $\mathbf{x}_i$ contain $n$ bits, then this takes time that is exponential in $n$. Is there a polynomial time algorithm?