Total Unimodularity

When every LP vertex is an integer point.

The idea

Total unimodularity identifies the constraint matrices for which a linear program returns integer answers on its own. A linear program's optimum is a vertex of $\{x : A x \le b,\ x \ge 0\}$, and a corner of a polyhedron need not have whole-number coordinates. That matters whenever the variables count things — trucks to dispatch, edges to use — because a fractional answer cannot be carried out, and rounding it can land outside the feasible region or far from the optimum.

Definition (Totally unimodular matrix).

A matrix $A$ is totally unimodular when every square submatrix of $A$ has determinant in $\{-1, 0, 1\}$.

The $1 \times 1$ submatrices are the entries, so in particular every entry is $-1$, $0$ or $1$ — but that alone is not sufficient, since the condition must hold at every size.

Theorem (Hoffman–Kruskal theorem).

If $A$ is totally unimodular and $b$ is an integer vector, then every vertex of the polyhedron $\{x : A x \le b,\ x \ge 0\}$ has integer coordinates.

So the linear program has already answered the integer question. The definition forces integrality through Cramer's rule. A vertex is the solution of $A' x = b'$ for some invertible square submatrix $A'$ of the constraints, so $x = (A')^{-1} b'$, and Cramer's rule writes each coordinate as a ratio of determinants with $\det A'$ in the denominator. When $\det A' = \pm 1$ and $b'$ has integer entries, that ratio is an integer.

Ways to work on it

• Walkthrough. The definition, a non-example, and the integrality payoff for linear programs.
• Practice. Decide whether a small matrix is totally unimodular.
• Hardest. Certify that a directed incidence matrix is totally unimodular and read off integrality.

Not sure where to start? Take the ten-question placement test.