Are integer linear *feasibility* problems NP-hard?

Question

I know that Integer Linear Programming problems are NP-hard. But it seems like this answer is only applicable to Integer Linear optimization problems.

It seems like integer linear feasibility problems should be able to be solved in polynomial time.

I was thinking that this would look something like this:

1. Solve the linear feasibility problem normally, and get the solution space.
2. Then, see if there is an integer solution point in this solution space.

This seems like it should be a polynomial time algorithm.

Does anyone know what I am missing here? Or have any papers that could help?

Answer 1

Feasibility of integer linear programming (ILP) is also NP-hard.

(Why? See https://cs.stackexchange.com/a/29916/755, Is 0-1 integer linear programming NP-hard when $c^T$ is the all-ones vector?, which reduces the SAT problem to feasibility of ILP. Or, alternatively, note that if you could test feasibility of ILP in polynomial time, then you could solve all ILPs in polynomial time too. In particular you could find the optimal value of the objective function $\Phi$ by using binary search: add the inequality $\Phi \ge c$ for some constant $c$ to your ILP, and then use binary search on $c$ to find the largest $c$ for which this system is feasible.)

You can't solve ILP using a linear programming solver. To put it another way, there is no known polynomial-time algorithm to "see if there is an integer solution point in [the] solution space" to a linear program -- that is exactly the ILP problem, which is known to be NP-hard.

To help you build your intuition, check out the examples in Linear programming vs integer linear programming.