I'm working on a set of problems for which I can formulate binary integer programs. When I solve the linear relaxations of these problems, I always get integer solutions. I would like to prove that this is always the case. I believe that this involves proving that the constraint matrix is totally unimodular. Is there any sufficent conditions for binary matrices to be totally unimodular that might be of use for this?
Here are some common ways of proving a matrix is TU.
There are other if-and-only-if conditions like Ghouila-Houri too (see Schrijver 1998) but the 4 conditions I gave above have been the most practical for me.