I have an ILP (all variables are binary) and on several instances I’ve observed that its optimal value coincides with the LP relaxation optimal value.
The LP relaxation is not integral for fractional optimal solutions are attained.
I’d like to prove that what I have observed is actually true. I suppose I’ll have to check some conditions on the polytope of the relaxation as well as the objective function, but I do not know where to start.
I’ve been trying to search for some results in these kind of problems, but I’ve found none. Has someone of you faced this problem (or a similar one)? Or do you know some result or some idea on how to prove this type of statement?