I am solving an integer program (IP) whose constraint matrix is not totally unimodular (TU). The linear programming (LP) relaxation and the original IP always have the same optimal solution, or the LP relaxation is always optimal — in the hundreds of random instances I chose. Since the constraint matrix is not TU, I do not have a sufficient condition to verify if indeed this should always hold true or not (since TU is only a sufficient condition and not necessary).
Since I am unable to find a counterexample, my questions are:
What other tests exist (such as TU) by which I can check if the LP solution should always solve the IP or not?
We also have a proof that this problem is NP complete. Does it follow that the LP relaxation cannot solve this IP?