Total Unimodularity
Interactive visualizations for Chapter 7 of the Ricerca Operativa notes
Integral vs Non-Integral Polyhedra
The central question of Chapter 7 is: when does solving the LP relaxation automatically give an integer solution? The answer depends on whether the feasible polyhedron is integral — meaning all its vertices land on the integer lattice \(\mathbb{Z}^n\).
Consider two polyhedra in \(\mathbb{R}^2\):
- \(P_1\) (integral): \(\{(x_1, x_2) : x_1 + x_2 \leq 3,\; x_1, x_2 \geq 0\}\) — vertices \((0,0)\), \((3,0)\), \((0,3)\), all integer.
- \(P_2\) (non-integral): \(\{(x_1, x_2) : 2x_1 + 2x_2 \leq 3,\; x_1, x_2 \geq 0\}\) — vertices \((0,0)\), \((\tfrac{3}{2},0)\), \((0,\tfrac{3}{2})\), two of which are fractional.
The constraint matrix of \(P_1\) is \(A_1 = \begin{pmatrix}1 & 1\end{pmatrix}\), which is totally unimodular (TUM). The matrix of \(P_2\) is \(A_2 = \begin{pmatrix}2 & 2\end{pmatrix}\), which is not TUM (entries must lie in \(\{0, \pm 1\}\)). The TUM property of \(A\) is exactly what forces integrality for every integer right-hand side \(b\).
Bipartite Graph and Its Incidence Matrix
An undirected bipartite graph \(G = (U \cup W, E)\) has its vertices split into two independent sets \(U\) and \(W\), with every edge connecting a vertex in \(U\) to one in \(W\). The vertex-edge incidence matrix \(A\) has \(a_{ie} = 1\) if vertex \(i\) is an endpoint of edge \(e\), and \(0\) otherwise.
The incidence matrix of a bipartite graph is always TUM. Why? Each column (edge) has exactly two \(+1\) entries (one per endpoint), so the sufficient conditions for TUM are satisfied with the partition \(R_1 = U\), \(R_2 = W\): since both endpoints of any edge have the same sign (\(+1\)), requiring them to be in different sets exactly matches the bipartition structure.
We work with the bipartite graph:
- Left partition \(U\): \(u_1, u_2, u_3\)
- Right partition \(W\): \(w_1, w_2, w_3\)
- Edges: \(e_1 = \{u_1, w_1\}\), \(e_2 = \{u_1, w_2\}\), \(e_3 = \{u_2, w_1\}\), \(e_4 = \{u_2, w_3\}\), \(e_5 = \{u_3, w_2\}\)
Why TUM? Each column of \(A\) has exactly two \(1\)s (one in the \(U\) block, one in the \(W\) block). Using the sufficient conditions with \(R_1 = U\) and \(R_2 = W\): each column’s two \(+1\)s have the same sign, so the rows must be in different sets — which is guaranteed by the bipartite structure. Therefore \(A\) is TUM, and the LP relaxation of any matching or assignment problem on this graph solves the ILP for free.
Node-Arc Incidence Matrix of a Directed Graph
For a directed graph \(G = (V, E)\), the node-arc incidence matrix \(A\) has \(a_{ie} = +1\) if arc \(e\) leaves node \(i\), \(a_{ie} = -1\) if arc \(e\) enters node \(i\), and \(0\) otherwise. Every column (arc) has exactly one \(+1\) and one \(-1\), so the column sum is always zero.
This matrix is always TUM. The proof uses the sufficient conditions with the trivial partition \(R_1 = \text{all rows}\), \(R_2 = \emptyset\): each column’s two non-zero entries have different signs (\(+1\) and \(-1\)), so they must be in the same set — which holds since every row is in \(R_1\).
We work with the directed graph \(G\) on nodes \(\{1, 2, 3, 4\}\) and arcs:
- \(e_1 = (1 \to 2)\), \(e_2 = (1 \to 3)\), \(e_3 = (2 \to 3)\), \(e_4 = (2 \to 4)\), \(e_5 = (3 \to 4)\)
Determinants of Square Submatrices
The definition of TUM requires every square submatrix to have determinant in \(\{0, +1, -1\}\). The visualization below computes all \(2 \times 2\) submatrices of the node-arc incidence matrix above and displays their determinants, confirming the TUM property directly.
Conclusion: Every \(2 \times 2\) submatrix (and by the theorem, every square submatrix of any size) of the node-arc incidence matrix has determinant in \(\{0, +1, -1\}\). This confirms that node-arc incidence matrices of directed graphs are always TUM — which is why shortest-path, maximum-flow, and minimum-cost-flow problems can be solved as LPs, with the guarantee that the LP optimum is always integer when \(b\) is integer.