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

Question

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

Answer 1

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.

Answer 2

There are instances of size n that can be solved in time $t ≤ 2n+2$, $t ≤ (2n+2)^2$, $t ≤ (2n+2)^3$, $t ≤ (2n+2)^4$ etc. Every instance can be solved in $t ≤ (2n+2)^k$ if we pick k large enough for that instance.

Let $I_k$ be the class of all instances that can be solved in $t ≤ (2n+2)^k$, where n is the instance size. Then each class $I_k$ can be solved in polynomial time. And since the union of all classes $I_k$ covers all instances, each instance can be solved "in polynomial time".

That's true for any problem that can be solved. It just means that asking if one particular instance can be solved "in polynomial time" doesn't make much sense.

Now you can of course take any k-th degree polynomial $P_k (n)$, an algorithm to solve ILP, and for every instance I check if the algorithm solves I in $P_k(n)$ where n is the size of I by just running the algorithm until either a solution is found or $P_k(n)$ has been spent. Again, not very valuable.