How tell if a polyhedron contains a lattice point

Question

So given a polyhedron

$Ax \le b$

Is there an Algorithm or formula to determine whether said polyhedron contains a lattice point (integer point)

I was thinking a couple things:

1. brute force neighborhood search (I don't like this idea)
2. Try to prove that at least 1 unit cube (of same dimension as polyhedron) can be contained in polyhedral space. Aka check if all dimensions between 2 faces $\ge$ 1
3. #2 doesn't always work so I need a fail-safe.

Has this been done before? I am not interested in finding the point, I just merely wish to know of one is present.

Answer 1

This is called Integer Linear Programming. Note that the problem of determining whether $Ax\leq b$ contains a lattice point is asymptotically basically as hard as a maximization function with the same parameters. This problem is NP-hard, so it is expected that there is no polynomial time algorithm for it.

Edit: ILP can be reduced to this using binary search methods. We start by finding the maximum $B$ and minimum $b$ of the relaxed LP problem (if the set $Ax\leq b$ is unbounded, other bounds are needed which I will not discuss here). We can determine whether there is an integer solutions with $f(x)\ge c$ by checking whether the polytope $-f(x)\leq -c, Ax\leq b$ contains an integer point. Using this we can in polynomial time (assuming calls to the satisfiability routine run in constant time) get any exponential accuracy for the integer maximum.