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:
- Solve the linear feasibility problem normally, and get the solution space.
- 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?