I have a problem that I managed to write as a binary integer linear program. As a natural first step, I relaxed the integrality constraint to solve a regular LP. To my surprise, the solutions where all integral (either $0$ or $1$).
I then ran some simulations on random instances of my problem and, to my surprise, all were integral.
I started looking into the constraint matrix to try to prove it is totally unimodular, but managed to find a counterexample [An instance whose constraint matrix is not totally unimodular].
So I am left puzzled. I've been running simulations for the past two days on random instances of the problem in hope to find a counterexample [Where the solution of the LP are non integral] to no avail.
What is the next step after total unimodularity that you can explore to prove that the solution of an LP formulation is integral?
When TUM fails, you try a weaker notion called Total Dual Integrality (https://en.wikipedia.org/wiki/Total_dual_integrality)