Total Unimodularity

(You can watch the video version of this post on YouTube.)

Now there’s a property of matrices called “unimodularity” and a variant I want to talk about today called total unimodularity. The definition is a bit opaque: a matrix is totally unimodular if every square submatrix has determinant 0, +1 or −1. It doesn’t really help that I don’t have a great intuition about determinants, but here’s the thing.

Let $A$ be a totally unimodular matrix and $b$ an integer. Then the standard linear program with $Ax\leq b$ is integral, that is, all extreme points of the feasible region have integer coordinates and optimising a linear objective function will necessarily give an integral solution – as long as your solver is going to give you an extreme-point solution, it’s going to be integer. No need to get out the ILP solver.

Don’t get me wrong, total unimodularity is a pretty restrictive condition. To be perfectly honest, whenever I’ve checked, uh, my LP coefficients never actually were. But still. If you’re ever doing a kinda-simple linear program, maybe check to see if it’s totally unimodular. You might have more luck and get a polynomial-time algorithm for free.

Let’s finish up with some examples. The LP for matching is totally unimodular, and so is the LP for network flow. Then there is some condition with blocks of consecutive 1s or -1s, but: I’m not even going to go there. Just look it up if you ever need to.