I have a linear program (LP) for which the constraint matrix is NOT totally unimodular (TU). However, even though constraint matrix is small (14x20), extensive generation of random coefficients for objective function did not allow me to find the problem formulation for which optimal solution value changes if I add integrality constraints.
I believe that the reason might be that I also have some constraints on the objective function coefficients - I know that some coefficients are 0'os, and some coefficients are equal.
Given that, I wanted to know if it is possible to prove that given my specific subset of objective functions the objective will always be integral, and what should be the way to do that.
Provided that my hypothesis is true, I also wanted to ask if it is easy to find an integer solution, given the solution of an LP, if I know that the objective function value will be the same. (Some kind of movement on the hyperplane of active constraints?)
Any relevant literature links are appreciated.