How to check if a specific ILP problem can be solved in polynomial time or not?

How can we know that a specific ILP problem is solvable in polynomial time or not given the constraints?

First of all, let me start by making clear that the notion of 'solvable in polynomial time' is something defined on a class of problem instances. It makes no sense to speak of polynomial time for a single problem as any single problem can be solved in $O(1)$!

That said, there is a notable class of ILP's that is known to be polynomial time solvable. This class consists of the ILP's that can be described with a totally unimodular matrix (or equivalently, if the solution space is an integral polyhedron). This property guarantees that the relaxed version of the ILP has in fact the same solution as the original ILP!

However, this doesn't mean that there aren't other classes of ILP's for which there exists an algorithm that can solve them in polynomial time (In fact, as it is possible that P=NP, it is possible that the class of all ILP's is solveable in polynomial time!)

So, in general, a complete answer to your question is beyond the current state of science, but there are special cases where can say that it is poly-time solvable. However, we cannot say for sure that there even exist classes that are not.

StackExchange Computer Science Q#89140, answer score: 7