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?
TU is one of the nice properties that can guarantee LP relaxation solves the integer programs. Generally speaking, if one can find the convex hull description, then the integer program can be solved as linear program. For example, the uncapacitated lot sizing (ULS) problem with $(l,s)$ inequalities, see Barany at al. 1984). The $(l,s)$ inequalities define the facet of the ULS and together with the original description of ULS give the convex hull, hence the formulation still give integer solutions without integer restriction. Another example is the convex hull description for uncapacitated lot sizing problem with backlogging (see Kucukyavuz and Pochet 2009).
So I don't know what your problem is, but it is possible all the constraints are facet-defining therefore even if it is not TU, it still solves the problem as LP.
Finding convex hull is problem specific and it is very challenging since many complicated problems might have exponential number of facet-defining inequalities in their convex hull description. A more practical way is to find several strong facet-defining inequalities and develop efficient separation algorithm inside the branch-and-cut algorithm to achieve $0\%$ optimality gap within reasonable time limit, e.g., $1$ hour. Another way to find convex hull is to construct extended formulation through projection since extended formulation very often is more compact (but not necessary).