Section 6.2 Totally Unimodular Matrices
Since many discrete optimization problems can be phrased as integer linear programs, but solving ILPs is NP-hard, it is useful to identify classes of ILPs for which the ILP and its LP relaxation are guaranteed to have the same value. This motivates the following definitions. First, a submatrix of a matrix \(A\) is any matrix that can be obtained from \(A\) by deleting some rows and columns. A matrix \(A\) is totally unimodular if all of its square submatrices have determinant equal to \(0,1\) or \(-1\text{.}\) Note that each entry is a \(1\times 1\) submatrix and so must be equal to \(0,1\) or \(-1\text{.}\) The following lemma explains why these matrices are so useful for reducing ILP problems to LP problems.
Proof.
Let \(a_1,\dots,a_m\) be the rows of \(A\) and let \(z\) be a vertex of \(P\text{.}\) Then, by Lemma 2.1.10, \(A_z\) has rank \(n\text{.}\) Therefore, there exist \(n\) linearly independent rows of \(A\) such that, for any such row \(a_i\text{,}\) we have \(a_iz=b_i\text{.}\) Let \(A_z'\) be the square matrix consisting of these rows and let \(b'\) be the restriction of \(b\) to the same \(n\) rows. Then \(A_z'\) has rank \(n\) and so it is invertible. Since \(A\) is totally unimodular, it follows that \(A_z'\) has determinant equal to \(1\) or \(-1\) and all entries of \(A_z'\) are integers (in fact, they are all \(0,1\) or \(-1\)). If a matrix has determinant equal to \(1\) or \(-1\) and all of its entries are integers, then the same is true for its inverse; see Exercise 5. So, \((A_z')^{-1}\) is an integer matrix. Finally, since \(b\) is integer-valued, so is \(z=(A_z')^{-1}b'\) and we are done.
Recall that, when solving a linear program over a bounded polyhedron, the optimum is always attained at one of the corners. However, not all polyhedra are bounded, and they may not even have corners, and so it would be valuable to prove that the optimum of a linear program with constraints as in Lemma 6.2.3 is attained at an integer vector in this case as well. The following definition is useful.
Definition 6.2.2.
We say that \(P=\{x: Ax\leq b\}\) is an integer polyhedron if, for any vector \(c\text{,}\) either the function \(c^Tx\) is unbounded above on \(P\) or its maximum is achieved by an integer vector \(x\text{.}\)Let us now show how we can use Lemma 6.2.3 to deal with the unbounded case as well.
Lemma 6.2.3.
If \(A\) is a totally unimodular \(m\times n\) matrix and \(b\in\mathbb{Z}^m\text{,}\) then \(P=\{x:Ax\leq b\}\) is an integer polyhedron.Proof.
Let \(c\in\mathbb{R}^n\) and suppose that there exists \(x\) which maximizes \(c^Tx\) over \(x\in P\) (i.e. we assume that the value of the LP is not \(\infty\)). Let \(y\) and \(z\) be integer valued vectors such that \(y\leq x\leq z\text{.}\) Now, consider the linear program
\begin{align*}
\text{max } \amp \amp c^Tx\\
\text{subject to } \amp \amp \begin{bmatrix}A\\-I\\I\end{bmatrix}x\leq \begin{bmatrix}b\\-y\\z\end{bmatrix}
\end{align*}
The matrix \(\begin{bmatrix}A\\-I\\I\end{bmatrix}\) is totally unimodular by several applications of Exercise 6. Also, the polytope given by the constraints of this LP is bounded. So, by Lemma 6.2.1, the above LP is maximized by an integer vector. Since \(x\) is feasible for this LP, its value of this is equal to the value of the original LP. So, the original LP is maximized by an integer vector and the proof is complete.
Corollary 6.2.4.
If \(A\) is a totally unimodular \(m\times n\) matrix and \(b\in\mathbb{Z}^m\text{,}\) then \(P=\{x:Ax\leq b, x\geq0\}\) is an integer polyhedron.Proof.
By Exercise 6, if we incorporate the non-negativity constraints into the constraint matrix, then it remains totally unimodular. So, the result follows from Lemma 6.2.3.
From this, we can also get sufficient conditions for a primal LP and its dual to both have integer optima.
Lemma 6.2.5.
Let \(A\) be a totally unimodular \(m\times n\) matrix, let \(b\in\mathbb{Z}^m\) and let \(c\in\mathbb{Z}^n\text{.}\) Suppose that the linear program
\begin{align*}
\text{max } \amp \amp c^Tx\\
\text{subject to } \amp \amp Ax\leq b\\
\amp \amp x\geq0
\end{align*}
and its dual
\begin{align*}
\text{min } \amp \amp b^Ty\\
\text{subject to } \amp \amp A^Ty\geq c\\
\amp \amp y\geq0
\end{align*}
are both feasible. Then both the primal LP and its dual are optimized by integer valued vectors.Proof.
Since the dual is feasible, the value of the primal is finite. So, by Corollary 6.2.4, the primal is optimized by an integer vector. The dual is handled similarly where, here, we use the fact that \(A^T\) is totally unimodular as well since the determinant of a matrix is equal to the determinant of its transpose.
Here is a YouTube video related to this section:
