Question

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?

Answer 1

Here are some common ways of proving a matrix is TU.

1. The incidence matrix of a bipartite graph and network flow LPs are TU; these are standard examples usually taught in every book on TU.

2. The consecutive-ones property: if it is (or can be permuted into) a 0-1 matrix in which for every row, the 1s appear consecutively, then it is TU. (The same holds for columns since the transpose of a TU matrix is also TU.)

3. Every "network matrix," defined as follows, is TU (and they are a fundamental building block of the set of all TU matrices, according to Seymour's theorem). The rows correspond to a tree $T = (V, R)$ each of whose arcs have an orientation (i.e. it is not necessary that exist a root vertex $r$ such that the tree is "rooted into $r$" or "out of $r$").The columns correspond to another set $C$ of arcs on the same vertex set $V$. To compute the entry at row $R$ and column $C = st$, look at the $s$-to-$t$ path $P$ in $T$, then the entry is:

   • +1 if arc $R$ appears forward in $P$
   • -1 if arc $R$ appears backwards in $P$
   • 0 if arc $R$ does not appear in $P$

   [You can see more in Schrijver's 2003 book.]

4. Ghouila-Houri showed a matrix is TU iff for every subset $R$ of rows, there is an assignment $s : R \to \pm 1$ of signs to rows so that the signed sum $\sum_{r \in R} s(r)r$ (which is a row vector the same width as the matrix) has all its entries in $\{0, \pm1\}$.

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.