Totally Unimodular Matrices

Definition of totally unimodular (TU) matrices, the Heller-Tompkins sufficient condition, and the Hoffman-Kruskal integrality theorem. When the constraint matrix of an LP is totally unimodular and the right-hand side is integer, every vertex of the feasible region is integer — so the LP relaxation automatically delivers an integer optimum and the integrality gap is zero.

Step 1 of 157%

Tutorial

Definition of Total Unimodularity

Total unimodularity is the strongest structural property a constraint matrix can have for integer programming: when it holds, the LP relaxation automatically delivers an integer optimum.

A matrix $A \in \mathbb{R}^{m \times n}$ is totally unimodular (abbreviated TU) if the determinant of every square submatrix of $A$ lies in $\{-1, 0, 1\}$ .

A submatrix is obtained by selecting any subset of rows and any subset of columns of $A$ and keeping only the entries at their intersections. Since each entry of $A$ is a $1 \times 1$ submatrix, every entry of a TU matrix must lie in $\{-1, 0, 1\}$ .

For example, consider

A = \begin{bmatrix} 1 & -1 & 0 \\ -1 & 0 & 1 \end{bmatrix}.

All entries lie in $\{-1, 0, 1\}$ . The three $2 \times 2$ submatrices have determinants

\begin{vmatrix} 1 & -1 \\ -1 & 0 \end{vmatrix} = -1, \quad \begin{vmatrix} 1 & 0 \\ -1 & 1 \end{vmatrix} = 1, \quad \begin{vmatrix} -1 & 0 \\ 0 & 1 \end{vmatrix} = -1.

Every submatrix determinant is in $\{-1, 0, 1\}$ , so $A$ is totally unimodular.