# Integer point in a non-empty polytope

I have a high-dimensional, non-empty polytope $Ax\geq b$ sitting inside the cube ($0\leq x_i \leq 1$). Is there any general theory or technique to show that this polytope contains an integer point, that is a point of the cube?

Unfortunately, $A$ is not totally unimodular.

Thanks,

Richard

• This problem is NP-complete, so you're unlikely to find a good algorithm without more info about how the polytope is constructed. – Suresh Venkat Mar 6 '14 at 19:12

You could answer the question by trying all $2^n$ possible vectors with 0/1 entries (where $n$ is the dimension of the space), but let's assume you mean "is there an efficient algorithm to determine if an integer point exists?" The answer is basically "no"; the relevant area to look at is (binary) mixed integer linear programming.