Three times now a linear program has returned whole numbers without being asked. The path program of Chapter 2 had an optimal solution with entries \(0\) and \(1\) . Maximum flows with integer capacities could be chosen integral. The assignment relaxation had an optimal permutation matrix. Each fact was proved by its own combinatorial argument, about paths, about augmentations, about Hall’s condition. Yet the cargo relaxation, which looks no more complicated, has the optimal solution \((3/2,13/4)\) .
What distinguishes the first three from the fourth is not the objective and not the right-hand side. It is the constraint matrix, and the property can be stated in one line: every square submatrix has determinant \(0\) , \(1\) , or \(-1\) . This chapter shows why that property forces every vertex of the feasible region to be an integer vector, gives practical tests for it, and re-derives the integrality theorems of Chapters 2 to 4, together with König’s theorem, as instances of one statement. It also marks the boundary: the triangle that defeated the matching relaxation in Chapter 4 fails the test by having a determinant equal to \(2\) .
6.1 Vertices are solutions of square systems
Recall from Continuous Optimization that a vertex, or extreme point, of a convex set is a point of the set that is not the midpoint of two other points of the set, and that a linear program over a polyhedron that has vertices, if it has an optimal solution at all, has one at a vertex. That course characterized vertices for the standard equality form. We need the same result for inequality form.
Theorem 6.1 (vertices and active constraints). Let \(P=\{x\in\mathbb R^n:Ax\le b\}\) and \(\bar x\in P\) . Call a row \(a_i^{\top}x\le b_i\) active at \(\bar x\) if \(a_i^{\top}\bar x=b_i\) . Then \(\bar x\) is a vertex of \(P\) if and only if the active rows include \(n\) linearly independent ones. In that case \(\bar x\) is the unique solution of the square system \(A'x=b'\) formed by any \(n\) linearly independent active rows.
Proof. Suppose the active rows include \(n\) linearly independent ones, forming \(A'x=b'\) , and suppose \(\bar x=\tfrac12(v+w)\) with \(v,w\in P\) . For each active row, \(a_i^{\top}v\le b_i\) and \(a_i^{\top}w\le b_i\) , while their average is \(a_i^{\top}\bar x=b_i\) ; so both hold with equality. Thus \(v\) and \(w\) both solve \(A'x=b'\) , which has only one solution because \(A'\) is nonsingular. Hence \(v=w=\bar x\) and \(\bar x\) is a vertex.
Conversely, suppose the active rows span a space of dimension less than \(n\) . Then some \(d\ne 0\) satisfies \(a_i^{\top}d=0\) for every active row. Every inactive row has \(a_i^{\top}\bar x<b_i\) , so for a small enough \(\varepsilon>0\) both \(\bar x+\varepsilon d\) and \(\bar x-\varepsilon d\) satisfy all rows: the active ones are unchanged and the inactive ones still have slack. These are two different points of \(P\) with midpoint \(\bar x\) , so \(\bar x\) is not a vertex.
The theorem turns a geometric question into arithmetic. Every vertex has the form \((A')^{-1}b'\) for a nonsingular \(n\times n\) submatrix \(A'\) of \(A\) , with \(b'\) the matching part of \(b\) . Whether vertices are integral is a question about what inverses of square submatrices do to integer vectors.
Example 6.1: The cargo vertices, by determinants
Write the cargo relaxation as four rows in two variables: \(x_1+2x_2\le 8\) , \(3x_1+2x_2\le 11\) , \(-x_1\le 0\) , \(-x_2\le 0\) . With \(n=2\) , each vertex is the solution of two rows taken as equations. There are six pairs.
Rows 1 and 2 give \(x=(3/2,13/4)\) , which is feasible. Rows 1 and 3 give \((0,4)\) , feasible. Rows 1 and 4 give \((8,0)\) , which violates row 2 since \(24>11\) . Rows 2 and 3 give \((0,11/2)\) , which violates row 1. Rows 2 and 4 give \((11/3,0)\) , feasible. Rows 3 and 4 give \((0,0)\) , feasible. So the polygon has four vertices, two integral and two not.
Now look at the determinants of the \(2\times 2\) matrices involved. For rows 3 and 4 it is \(1\) , and for rows 1 and 3 it is \(2\) , yet the vertex \((0,4)\) is integral, because \(8\) happens to be divisible by \(2\) . For rows 2 and 4 it is \(-3\) , and the vertex has a denominator of \(3\) . For rows 1 and 2,
and the vertex \((3/2,13/4)\) has denominators \(2\) and \(4\) . The denominators of a vertex divide the determinant of the system that defines it. A determinant of \(\pm 1\) would leave no room for fractions, whatever the right-hand side.
6.2 Integral polytopes
Definition 6.2 (integral polytope). A polytope is a bounded polyhedron. A polytope is integral if every one of its vertices is an integer vector.
Proposition 6.3 (three faces of integrality). For a nonempty polytope \(P=\{x:Ax\le b\}\) the following are equivalent: (a) \(P\) is integral; (b) for every \(c\in\mathbb R^n\) the linear program \(\max\{c^{\top}x:x\in P\}\) has an optimal solution that is an integer vector; (c) \(P=\operatorname{conv}(P\cap\mathbb Z^n)\) .
Proof. (a) implies (b): the linear program has an optimal vertex, and vertices are integral.
(b) implies (a): let \(\bar x\) be a vertex and let \(A'x\le b'\) be \(n\) linearly independent rows active at it. Take \(c\) to be the sum of those rows. For every \(x\in P\) , \(c^{\top}x\le\mathbf 1^{\top}b'\) , with equality only if every one of the \(n\) rows is active at \(x\) , that is, only if \(x=\bar x\) . So \(\bar x\) is the unique optimal solution for this \(c\) , and by (b) it is an integer vector.
(a) implies (c): a polytope is the convex hull of its vertices, a standard fact of polyhedral theory that we use without proof. If the vertices are integral they belong to \(P\cap\mathbb Z^n\) , so \(P\subseteq\operatorname{conv}(P\cap\mathbb Z^n)\subseteq P\) .
(c) implies (a): \(P\cap\mathbb Z^n\) is finite because \(P\) is bounded, and by Theorem 5.4(c) every extreme point of the hull of a finite set of integer points is one of those points.
Statement (c) says that an integral polytope is an ideal formulation, in the sense of Definition 5.5, of its own integer points. Statement (b) is the practical payoff: the relaxation solves the integer program for every objective, and the simplex method, which stops at a vertex, delivers an integer solution.
6.3 Determinants and total unimodularity
Two facts about determinants are needed, both from Linear Algebra: the determinant of a product is the product of the determinants, and the inverse of a nonsingular matrix \(B\) is its adjugate divided by \(\det B\) , where the entries of the adjugate are, up to sign, determinants of submatrices of \(B\) . In particular the adjugate of an integer matrix is an integer matrix.
Lemma 6.4 (when inverses preserve integrality). Let \(B\) be a nonsingular \(n\times n\) integer matrix. Then \(B^{-1}b\) is an integer vector for every integer vector \(b\) if and only if \(\det B=\pm 1\) .
Proof. If \(\det B=\pm 1\) , then \(B^{-1}\) equals plus or minus the adjugate of \(B\) , an integer matrix, so \(B^{-1}b\) is integral whenever \(b\) is. Conversely, if \(B^{-1}b\) is integral for every integral \(b\) , apply this to the unit vectors: every column of \(B^{-1}\) is integral, so \(\det(B^{-1})\) is an integer. Since \(\det(B)\det(B^{-1})=1\) and both factors are integers, \(\det B=\pm 1\) .
To make every vertex integral for every integer right-hand side, every nonsingular square submatrix that can define a vertex should have determinant \(\pm 1\) . The cleanest sufficient condition asks this of all square submatrices.
Definition 6.5 (totally unimodular matrix). A matrix \(A\) is totally unimodular if every square submatrix of \(A\) , of every size, has determinant \(0\) , \(1\) , or \(-1\) . In particular every entry of \(A\) , being a \(1\times 1\) submatrix, is \(0\) , \(1\) , or \(-1\) .
Lemma 6.6 (operations preserving total unimodularity). If \(A\) is totally unimodular, so are: every submatrix of \(A\) ; the transpose \(A^{\top}\) ; the matrix obtained by multiplying a row or column by \(-1\) ; and the matrices obtained by appending to \(A\) a row or column that is a unit vector, in particular the stacked matrix with \(A\) above an identity matrix or above its negative.
Proof. The first three hold because a square submatrix of the new matrix is, up to transposition or a change of sign of its determinant, a square submatrix of \(A\) . For the last, let \(B\) be a square submatrix of the enlarged matrix. If \(B\) does not meet the appended row, it is a submatrix of \(A\) . If it does, that row of \(B\) has at most one nonzero entry. If it has none, \(\det B=0\) . If it has one, equal to \(\pm 1\) , expanding the determinant along that row gives \(\det B=\pm\det B'\) where \(B'\) is a smaller square submatrix that no longer meets the appended row, hence a submatrix of \(A\) . Appending several unit rows is done one at a time.
Theorem 6.7 (total unimodularity gives integral vertices). Let \(A\) be totally unimodular and let \(b\) , \(\ell\) , and \(g\) be integer vectors. Then every vertex of each of the polyhedra
is an integer vector.
Proof. Each polyhedron has the form \(\{x:Dx\le d\}\) where \(d\) is an integer vector and \(D\) is obtained from \(A\) by stacking copies of \(A\) , \(-A\) , the identity, and the negative identity; for example the first is given by \(A\) above \(-I\) , with right-hand side \(b\) above \(0\) , the second writes \(Ax=b\) as \(Ax\le b\) and \(-Ax\le -b\) , and the bounds \(\ell\le x\le g\) of the third and fourth are the rows of \(I\) with right-hand side \(g\) and of \(-I\) with right-hand side \(-\ell\) . A square submatrix of such a \(D\) that contains a row together with its own negative, whether a row of \(A\) and of \(-A\) or a row of \(I\) and of \(-I\) , has determinant zero, and any other square submatrix is, after sign changes of rows, a square submatrix of \(A\) with unit rows appended. By Lemma 6.6 all its square submatrices have determinant \(0\) or \(\pm 1\) . By Theorem 6.1 a vertex is \((D')^{-1}d'\) for a nonsingular \(n\times n\) submatrix \(D'\) of \(D\) ; then \(\det D'=\pm 1\) , and Lemma 6.4 makes the vertex integral.
Hoffman and Kruskal proved that the condition is also necessary in the following sense: if \(A\) is an integer matrix and the first polyhedron has integral vertices for every integer vector \(b\) , then \(A\) is totally unimodular. We shall not need the converse. Applying Theorem 6.7 to a linear program and to its dual at once gives the form in which the theorem is most often used.
Corollary 6.8 (integral primal and dual optima). Let \(A\) be totally unimodular and let \(b\) and \(c\) be integer vectors. If the linear programs
have optimal solutions, then both have optimal solutions that are integer vectors, and the two optimal values are equal.
Proof. The feasible regions lie in the nonnegative orthant, so they contain no line and have vertices, and each program has an optimal vertex. The primal vertex is integral by Theorem 6.7. The dual region is \(\{y:-A^{\top}y\le -c,\ y\ge 0\}\) , and \(-A^{\top}\) is totally unimodular by Lemma 6.6, so the dual vertex is integral too. Equality of the values is strong duality for linear programs.
A statement of the form “the maximum of one integer quantity equals the minimum of another” is called a min-max theorem. Corollary 6.8 manufactures one from every totally unimodular matrix.
6.4 Recognizing totally unimodular matrices
Checking the definition directly is hopeless except for tiny matrices: a \(6\times 8\) matrix has \(3002\) square submatrices. Two structural criteria cover most matrices that arise from networks.
Theorem 6.9 (two nonzeros per column). Let \(A\) have entries \(0\) , \(1\) , and \(-1\) , with at most two nonzero entries in each column. Suppose the rows can be split into two classes \(R_1\) and \(R_2\) such that, in every column with two nonzero entries, the two entries lie in the same class if they have opposite signs and in different classes if they have the same sign. Then \(A\) is totally unimodular.
Proof. We show by induction on \(k\) that every \(k\times k\) submatrix \(B\) has determinant \(0\) or \(\pm 1\) . For \(k=1\) this is the assumption on the entries. Let \(k\ge 2\) . If \(B\) has a zero column, \(\det B=0\) . If \(B\) has a column with exactly one nonzero entry, expand along that column: \(\det B=\pm\det B'\) with \(B'\) of size \(k-1\) , and the induction hypothesis applies. Otherwise every column of \(B\) has exactly two nonzero entries. Add the rows of \(B\) that belong to \(R_1\) and subtract those that belong to \(R_2\) . In each column, two entries of opposite sign lie in the same class and cancel; two entries of the same sign lie in different classes and cancel. The result is the zero vector, a nontrivial linear dependence among the rows of \(B\) , so \(\det B=0\) .
Corollary 6.10 (incidence matrices). (a) The node–arc incidence matrix of a directed graph, with a row for each node, a column for each arc, and entries \(+1\) at the tail and \(-1\) at the head of each arc, is totally unimodular. (b) The node–edge incidence matrix of a bipartite graph, with entries \(1\) at the two endpoints of each edge, is totally unimodular. (c) The node–edge incidence matrix of a graph that is not bipartite is not totally unimodular.
Proof. (a) Each column has one \(+1\) and one \(-1\) ; take \(R_1\) to be all rows and \(R_2\) empty. (b) Each column has two entries \(+1\) , one in a row of \(L\) and one in a row of \(R\) ; take \(R_1=L\) and \(R_2=R\) . (c) A graph that is not bipartite contains a cycle with an odd number \(k\) of nodes. The rows of those nodes and the columns of the cycle’s edges form a \(k\times k\) submatrix in which, after ordering nodes and edges around the cycle, row \(i\) has ones in columns \(i\) and \(i-1\) (cyclically). Expanding along the first row gives two triangular determinants and \(\det=1+(-1)^{k+1}\) , which is \(2\) for odd \(k\) .
Example 6.2: The streaming network’s matrix
For the network of Example 3.1, with nodes \(s,a,b,c,d,t\) and arcs in the order \((s,a)\) , \((s,b)\) , \((a,b)\) , \((a,c)\) , \((b,d)\) , \((d,c)\) , \((c,t)\) , \((d,t)\) , the node–arc incidence matrix is
Every column has one \(+1\) and one \(-1\) , so \(N\) is totally unimodular by Corollary 6.10(a), without inspecting any of its \(3002\) square submatrices. To see the mechanism once, take rows \(a,b,c\) and the columns of \((s,a)\) , \((a,b)\) , \((a,c)\) :
a triangular matrix. And rows \(a,b,c,d\) with the columns of \((a,b)\) , \((a,c)\) , \((b,d)\) , \((d,c)\) , the arcs of a cycle in the underlying undirected graph, give a matrix in which every column has both of its nonzeros; its rows add to zero and its determinant is \(0\) .
The maximum-flow problem on this network maximizes a linear function subject to conservation equations, whose matrix consists of the rows of \(N\) for \(a,b,c,d\) , and bounds \(0\le x\le u\) . By Theorem 6.7 in its fourth form, equations with integer bounds on the variables, integer capacities give integral vertices. This is Theorem 3.7 again, now with no reference to augmenting paths, and it applies equally to minimum-cost flows with integer supplies and capacities.
Example 6.3: The triangle, and a determinant equal to two
The node–edge incidence matrix of a triangle, with rows for the nodes and columns for the edges, is
The matching relaxation is \(\{x\ge 0:Tx\le\mathbf 1\}\) . Taking all three rows active gives the point \(T^{-1}\mathbf 1\) . Since
that point is \((\tfrac12,\tfrac12,\tfrac12)\) : it is feasible, three linearly independent rows are active, and so by Theorem 6.1 it is a vertex. It is the fractional matching of total weight \(\tfrac32\) met at the end of Chapter 4, and the \(\tfrac12\) in it is the reciprocal of the determinant.
Common mistake. Assuming that a matrix with entries \(0\) and \(1\) is totally unimodular. The triangle matrix has only such entries and determinant \(2\) . Total unimodularity is a condition on every square submatrix; entries in \(\{0,1,-1\}\) are merely the \(1\times 1\) case. Use a structural criterion, Theorem 6.9 or Theorem 6.11, or exhibit a submatrix with a determinant outside \(\{0,1,-1\}\) .
The second criterion concerns matrices whose columns are intervals.
Theorem 6.11 (consecutive ones). A matrix with entries \(0\) and \(1\) in which the ones of each column occupy consecutive rows is totally unimodular. The same holds if the ones of each row occupy consecutive columns.
Proof. A square submatrix \(B\) of such a matrix again has consecutive ones in each column, since deleting rows keeps the surviving ones of a column adjacent. Replace each row of \(B\) , from the last up to the second, by itself minus the row above it. These row operations do not change the determinant. A column whose ones occupied rows \(p\) to \(q\) now has \(+1\) in row \(p\) , \(-1\) in row \(q+1\) if that row exists, and zeros elsewhere. The new matrix has entries \(0,\pm 1\) and at most two nonzeros per column, of opposite signs, so Theorem 6.9 applies with \(R_2\) empty, and its determinant is \(0\) or \(\pm 1\) . The statement for rows follows by transposition.
Example 6.4: Shifts that are intervals
A help desk needs at least \(2,3,4,2,1\) agents in five consecutive periods. Six shift types are available, each covering a run of periods: shift 1 covers periods \(1\) –\(2\) at cost \(3\) ; shift 2 covers \(2\) –\(4\) at cost \(5\) ; shift 3 covers \(3\) –\(5\) at cost \(5\) ; shift 4 covers \(1\) –\(3\) at cost \(4\) ; shift 5 covers \(4\) –\(5\) at cost \(3\) ; shift 6 covers \(2\) –\(3\) at cost \(3\) . With \(x_j\) the number of agents on shift \(j\) , the problem is to minimize \(3x_1+5x_2+5x_3+4x_4+3x_5+3x_6\) subject to \(Ax\ge b\) , \(x\ge 0\) and integer, where
Each column has its ones in consecutive rows, so \(A\) is totally unimodular by Theorem 6.11, and so is \(-A\) . The relaxation’s vertices are integral by Theorem 6.7. Solving the relaxation gives \(x=(0,1,1,2,0,0)\) : two agents on shift 4 and one each on shifts 2 and 3, at cost \(8+5+5=18\) . The coverage is \(2,3,4,2,1\) , exactly the requirement, and no integer programming was needed.
Now let the day wrap around. With three periods and three shifts, each covering two cyclically adjacent periods, the matrix is the triangle matrix \(T\) of Example 6.3 with its rows reordered: the ones of the shift covering the last and first periods are not consecutive. If one agent is needed in each period, the relaxation puts half an agent on each shift at cost \(\tfrac32\) , while two whole agents are needed. A small change in the pattern of the matrix, from intervals to circular intervals, destroys integrality.
6.5 Old theorems from one new one
With Theorem 6.7 and Corollary 6.8 the integrality results of the earlier chapters become consequences of the shape of a matrix.
Shortest paths and flows. The constraint matrices of the path program of Section 2.5, of the minimum-cost flow problem of Definition 2.7, and of the maximum-flow problem are node–arc incidence matrices or submatrices of them, with bounds on the variables. By the fourth form of Theorem 6.7, integer supplies and capacities give integral vertices. For maximum flow, Corollary 6.8 also makes the dual integral, and an integral dual solution assigns \(0\) or \(1\) to each node, a cut: the max-flow min-cut theorem is strong duality plus total unimodularity.
Assignment. The constraints of Definition 4.8 are \(Mx=\mathbf 1\) , where \(M\) is the node–edge incidence matrix of the complete bipartite graph on rows and columns. By Corollary 6.10(b) and Theorem 6.7 the vertices are integral, hence permutation matrices, which is the content of Corollary 4.12.
König’s theorem. Let \(M\) be the node–edge incidence matrix of a bipartite graph. A matching is an integer solution of \(Mx\le\mathbf 1\) , \(x\ge 0\) , and a vertex cover is an integer solution of \(M^{\top}y\ge\mathbf 1\) , \(y\ge 0\) . The linear programs
are dual to each other. By Corollary 6.8 both have integral optimal solutions with equal values: a matching and a cover of the same size. That is Theorem 4.5.
Example 6.5: König’s theorem by linear programming
For the interpreter graph of Example 4.1, \(M\) has ten rows, for interpreters \(1,\dots,5\) and meetings \(a,\dots,e\) , and ten columns, one per edge. Solving the primal relaxation by the simplex method returns a vector with entries \(0\) and \(1\) of total \(4\) : a maximum matching. Solving the dual returns \(y=1\) on the nodes \(3\) , \(4\) , \(a\) , \(b\) and \(y=0\) elsewhere, of total \(4\) : the cover found in Example 4.1 by alternating search. No rounding was involved in either program. For the triangle the same pair of programs has value \(\tfrac32\) on both sides, with all primal and all dual variables equal to \(\tfrac12\) , and neither a matching nor a cover has that size.
6.6 What the theorem does not say
Total unimodularity is a sufficient condition with exact hypotheses, and each can be dropped only at a price.
The right-hand side must be integral. In Figure 6.1 the middle polygon has a totally unimodular matrix and vertices such as \((\tfrac32,0)\) , because \(b\) is not integral. In applications this means integer capacities, supplies, and requirements.
The conclusion is about vertices, not about all feasible or all optimal points. A linear program with several optimal vertices has fractional optimal solutions between them; the average of two maximum flows in Example 3.1 was one. An algorithm that returns vertices, such as the simplex method, returns integral ones; an interior-point method may return a point in the middle of an optimal face.
The condition is far from necessary for a particular right-hand side. The cargo matrix is not totally unimodular, it even has an entry equal to \(3\) , yet with right-hand side \((8,11)\) replaced by \((8,12)\) the polygon’s vertices are \((0,0)\) , \((4,0)\) , \((2,3)\) , and \((0,4)\) , all integral. Integrality for one \(b\) is an accident of divisibility; total unimodularity gives it for all integer \(b\) .
Finally, adding a constraint can destroy the property. A network flow problem with one extra budget constraint, or with two commodities sharing capacities, no longer has a totally unimodular matrix, and its relaxation can be fractional. For such problems, and for the cargo problem, integrality has to be enforced by search or by additional inequalities. Those are the next two chapters.
Exercises
-
For the polyhedron \(x_1+x_2\le 4\) , \(x_1-x_2\le 1\) , \(x_1\ge 0\) , \(x_2\ge 0\) , list all six pairs of rows, solve each pair as equations, and use Theorem 6.1 to identify the vertices; give the determinant of each pair and say which vertex is fractional.
Solution
Number the rows: (1) \(x_1+x_2\le 4\) ; (2) \(x_1-x_2\le 1\) ; (3) \(-x_1\le 0\) ; (4) \(-x_2\le 0\) . With \(n=2\) , Theorem 6.1 says a feasible point is a vertex exactly when two linearly independent rows are active there.
Rows 1 and 2: adding gives \(2x_1=5\) , so \(x=(5/2,3/2)\) ; it satisfies rows 3 and 4, so it is a vertex. The determinant of the pair is \(1\cdot(-1)-1\cdot 1=-2\) . Rows 1 and 3: \(x=(0,4)\) ; row 2 gives \(-4\le 1\) , feasible; determinant \(1\) . Rows 1 and 4: \(x=(4,0)\) ; row 2 gives \(4\le 1\) , false, so not a vertex; determinant \(-1\) . Rows 2 and 3: \(x=(0,-1)\) , which violates row 4; determinant \(-1\) . Rows 2 and 4: \(x=(1,0)\) , feasible; determinant \(-1\) . Rows 3 and 4: \(x=(0,0)\) , feasible; determinant \(1\) .
The vertices are \((5/2,3/2)\) , \((0,4)\) , \((1,0)\) , and \((0,0)\) . The only fractional vertex is \((5/2,3/2)\) , and it is defined by the only pair of rows whose determinant is not \(\pm 1\) ; its denominators equal \(2\) , the absolute value of that determinant. The matrix with rows \((1,1)\) and \((1,-1)\) is not totally unimodular, although all its entries are \(\pm 1\) .
-
Decide whether each matrix is totally unimodular, using a criterion from Section 6.4 or exhibiting a square submatrix with determinant outside \(\{0,1,-1\}\) : (a) rows \((1,1,0)\) , \((0,1,1)\) , \((0,0,1)\) ; (b) rows \((1,1)\) , \((-1,1)\) ; (c) rows \((1,-1,0)\) , \((0,1,-1)\) , \((-1,0,1)\) ; (d) rows \((1,1,0)\) , \((1,0,1)\) , \((0,1,1)\) .
Solution
(a) Totally unimodular. In each column the ones occupy consecutive rows: column 1 has a one in row 1; column 2 in rows 1 and 2; column 3 in rows 2 and 3. Theorem 6.11 applies.
(b) Not totally unimodular. The matrix itself is a \(2\times 2\) submatrix with determinant \(1\cdot 1-1\cdot(-1)=2\) .
(c) Totally unimodular. Every column has exactly one \(+1\) and one \(-1\) : it is the node–arc incidence matrix of a directed triangle, so Corollary 6.10(a) applies. Its own determinant is \(0\) , since the rows add to zero.
(d) Not totally unimodular. It is the node–edge incidence matrix of a triangle, a graph that is not bipartite, and its determinant is \(1\cdot(0-1)-1\cdot(1-0)+0=-2\) . Theorem 6.9 does not apply: each column has two entries of the same sign, so the two rows of every column must lie in different classes, and three rows cannot be split into two classes with every pair separated.
Matrices (c) and (d) differ only in signs, which shows that the pattern of zeros does not determine total unimodularity.
-
Prove that if \(A\) is totally unimodular then the matrix obtained by duplicating a column of \(A\) is totally unimodular, and deduce that the matrix with \(A\) beside \(-A\) is totally unimodular.
Solution
Let \(A'\) be obtained from \(A\) by repeating column \(j\) , and let \(B\) be a square submatrix of \(A'\) . If \(B\) uses at most one of the two copies, it is a square submatrix of \(A\) , with determinant \(0\) or \(\pm 1\) . If \(B\) uses both copies, it has two equal columns and its determinant is \(0\) . So \(A'\) is totally unimodular. Repeating the argument, duplicating any number of columns preserves total unimodularity.
For the matrix with \(A\) beside \(-A\) : duplicate every column of \(A\) , which gives \(A\) beside \(A\) , totally unimodular by the first part. Then multiply each of the columns of the second copy by \(-1\) . By Lemma 6.6, changing the sign of a column preserves total unimodularity, since it changes each subdeterminant at most in sign. The result is \(A\) beside \(-A\) .
This is the fact needed to handle a free variable \(x=x^+-x^-\) with \(x^+,x^-\ge 0\) : the constraint matrix in the new variables is \(A\) beside \(-A\) , so splitting free variables does not endanger integrality.
-
Compute the determinant of the node–edge incidence matrix of a cycle on \(k\) nodes for \(k=3,4,5\) , with nodes and edges ordered around the cycle, and state the general formula.
Answer
With row \(i\) having ones in columns \(i\) and \(i-1\) (cyclically), the determinants are \(2\) , \(0\) , and \(2\) for \(k=3,4,5\) . In general the determinant is \(1+(-1)^{k+1}\) : \(2\) for odd cycles and \(0\) for even cycles. Other orderings change the sign at most.
-
A transportation problem has two factories with supplies \(5\) and \(7\) and three warehouses with demands \(4\) , \(3\) , \(5\) . Write its constraint matrix, explain using Corollary 6.10 why every vertex of its feasible region is integral, and find one vertex.
Hint
Variables \(x_{ij}\) for factory \(i\) and warehouse \(j\) ; rows \(x_{i1}+x_{i2}+x_{i3}=\) supply for each factory and \(x_{1j}+x_{2j}=\) demand for each warehouse. The matrix is the node–edge incidence matrix of the complete bipartite graph on two and three nodes, totally unimodular by Corollary 6.10(b); supplies and demands are integers, so Theorem 6.7 applies. One vertex: \(x_{11}=4\) , \(x_{12}=1\) , \(x_{22}=2\) , \(x_{23}=5\) , others zero.
-
The matrix with rows \((1,-1)\) , \((-1,1)\) , \((1,0)\) , \((0,1)\) is totally unimodular. For the system with right-hand side \((1,2,3,3)\) and \(x\ge 0\) list the six vertices, and repeat with right-hand side \((\tfrac32,\tfrac32,\tfrac52,3)\) , identifying which hypothesis of Theorem 6.7 the second system violates.
Solution
The system is \(x_1-x_2\le b_1\) , \(-x_1+x_2\le b_2\) , \(x_1\le b_3\) , \(x_2\le b_4\) , \(x\ge 0\) .
Right-hand side \((1,2,3,3)\) . Walking around the boundary: \((0,0)\) ; along \(x_2=0\) until \(x_1-x_2=1\) , at \((1,0)\) ; along \(x_1-x_2=1\) until \(x_1=3\) , at \((3,2)\) ; up to \(x_2=3\) , at \((3,3)\) ; left along \(x_2=3\) until \(-x_1+x_2=2\) , at \((1,3)\) ; along that line down to \(x_1=0\) , at \((0,2)\) . The six vertices are \((0,0)\) , \((1,0)\) , \((3,2)\) , \((3,3)\) , \((1,3)\) , \((0,2)\) , all integral, as Theorem 6.7 guarantees.
Right-hand side \((\tfrac32,\tfrac32,\tfrac52,3)\) . The same walk gives \((0,0)\) , \((\tfrac32,0)\) , \((\tfrac52,1)\) , \((\tfrac52,3)\) , \((\tfrac32,3)\) , \((0,\tfrac32)\) . Five of the six vertices are fractional.
The matrix is the same in both systems, and it is totally unimodular: each of its rows is a unit vector or has one \(+1\) and one \(-1\) , so it is the transpose of a matrix covered by Theorem 6.9 with unit columns appended. The second system violates the other hypothesis of Theorem 6.7, integrality of the right-hand side. Each vertex is \((D')^{-1}d'\) with \(\det D'=\pm 1\) , so \((D')^{-1}\) is an integer matrix, and it maps the fractional \(d'\) to a fractional point.
-
Find all vertices of \(\{x\ge 0:x_1+x_2\le 5,\ -x_1+x_2\le 2,\ x_1\le 3\}\) , identify the fractional one, and exhibit the \(2\times 2\) submatrix whose determinant explains its denominator.
Solution
Rows: (1) \(x_1+x_2\le 5\) ; (2) \(-x_1+x_2\le 2\) ; (3) \(x_1\le 3\) ; and \(x\ge 0\) . The vertices, found by intersecting consecutive boundary lines, are \((0,0)\) ; \((3,0)\) from row 3 and \(x_2=0\) ; \((3,2)\) from rows 1 and 3; the intersection of rows 1 and 2, where subtracting gives \(2x_1=3\) , so \(x=(3/2,7/2)\) ; and \((0,2)\) from row 2 and \(x_1=0\) . Each is feasible: for instance \((3/2,7/2)\) has \(x_1=3/2\le 3\) .
The fractional vertex is \((3/2,7/2)\) . It is defined by rows 1 and 2, whose matrix is
\[ \begin{pmatrix}1&1\\-1&1\end{pmatrix},\qquad\text{with determinant }1\cdot 1-1\cdot(-1)=2 . \]Its inverse is one half of an integer matrix, and the right-hand side \((5,2)\) has an odd sum, so the half does not cancel: \(x_1=(5-2)/2\) and \(x_2=(5+2)/2\) . With right-hand sides of equal parity, such as \((6,2)\) , the same pair of rows would give the integral point \((2,4)\) : a determinant of \(2\) permits fractions and does not force them.
-
Prove that the matrix of a system of the form “\(x_j-x_k\le b_{jk}\) for certain pairs” is totally unimodular, and conclude that if such a system with integer right-hand sides and integer bounds on the variables has a solution, it has an integer solution.
Solution
Each row of the system has the form \(x_j-x_k\le b_{jk}\) , so each row of the matrix \(A\) has one entry \(+1\) , one entry \(-1\) , and zeros elsewhere. Then \(A^{\top}\) has one \(+1\) and one \(-1\) in each column: it is the node–arc incidence matrix of the directed graph with a node for each variable and an arc from \(j\) to \(k\) for each constraint. By Corollary 6.10(a), \(A^{\top}\) is totally unimodular, and by Lemma 6.6 so is \(A\) .
Now suppose the system \(Ax\le b\) , \(\ell\le x\le g\) with \(b\) , \(\ell\) , \(g\) integral has a solution. Its solution set is a nonempty polyhedron, bounded because of the bounds on \(x\) , so it is a polytope and has a vertex. By Theorem 6.7, in its third form, every vertex is an integer vector. A vertex is in particular a solution, so an integer solution exists.
Systems of this kind express timing requirements such as “event \(j\) occurs at most \(b_{jk}\) time units after event \(k\) ”. The result says that with integer data, schedules never need fractional times. It is the dual face of Theorem 2.3: these are the constraints defining feasible potentials.
-
Explain what is wrong with the claim “the constraint matrix is totally unimodular and \(b\) is integral, so every optimal solution of the linear program is integral”, using the two maximum flows of Example 3.1.
Hint
Theorem 6.7 is about vertices. Example 3.1 exhibits two integral maximum flows, with \(x_{ab}=3\) and \(x_{ab}=0\) ; their average is a maximum flow with \(x_{ab}=\tfrac32\) . It is optimal and not integral, and it is not a vertex, being the midpoint of two other feasible points.
-
Explain what is wrong with the claim “every entry of the matrix is \(0\) or \(1\) and every column has exactly two ones, so by Theorem 6.9 it is totally unimodular”, and state the hypothesis of the theorem that the claim omits.
Hint
Theorem 6.9 also requires a split of the rows into two classes such that two equal-signed entries of a column lie in different classes. For a \(0\) –\(1\) matrix with two ones per column this says the graph whose edges are the columns is bipartite. The triangle matrix satisfies the stated properties and has determinant \(2\) .
-
A matrix has consecutive ones in each row. Without transposing, describe the column operations that play the role of the row operations in the proof of Theorem 6.11, and carry them out on the matrix with rows \((1,1,0,0)\) , \((0,1,1,1)\) , \((0,0,1,1)\) , \((1,1,1,0)\) .
Answer
Replace each column, from the last to the second, by itself minus the column to its left. A row with ones in columns \(p\) to \(q\) becomes \(+1\) in column \(p\) and \(-1\) in column \(q+1\) if it exists. The given matrix becomes the matrix with rows \((1,0,-1,0)\) , \((0,1,0,0)\) , \((0,0,1,0)\) , \((1,0,0,-1)\) , in which every row has at most one \(+1\) and one \(-1\) .
-
Four periods need \(3,2,4,1\) workers. Shifts cover periods \(1\) –\(2\) , \(2\) –\(3\) , \(3\) –\(4\) , and \(1\) –\(4\) at costs \(2,2,2,5\) . Explain why the relaxation of the covering problem has an integral optimal vertex, and find an optimal staffing plan with its cost.
Solution
Let \(x_1,\dots,x_4\) count the workers on the four shifts. The constraints are
\[ x_1+x_4\ge 3,\qquad x_1+x_2+x_4\ge 2,\qquad x_2+x_3+x_4\ge 4,\qquad x_3+x_4\ge 1,\qquad x\ge 0 . \]Each shift covers consecutive periods, so each column of the matrix has consecutive ones and the matrix is totally unimodular by Theorem 6.11. The requirements are integers, so by Theorem 6.7 every vertex of the relaxation is integral, and the relaxation, which is bounded below and feasible, has an optimal vertex.
To find an optimum, consider the long shift. Each worker on shift 4 costs \(5\) and replaces at most one worker in each of the constraints. With \(x_4=0\) : \(x_1\ge 3\) , \(x_3\ge 1\) , and \(x_2+x_3\ge 4\) ; the cheapest choice is \(x_1=3\) and \(x_2+x_3=4\) with \(x_3\ge 1\) , at cost \(2\cdot 3+2\cdot 4=14\) . With \(x_4=1\) : \(x_1\ge 2\) and \(x_2+x_3\ge 3\) , at cost \(5+4+6=15\) . Larger \(x_4\) costs more still. So the optimum is \(14\) , attained for example by \(x=(3,3,1,0)\) , with coverage \(3,6,4,1\) .
A certificate: prices \(2\) on period 1 and \(2\) on period 3 are feasible for the dual, since shift 1 covers period 1 only among these, at cost \(2\ge 2\) ; shifts 2 and 3 cover period 3, at cost \(2\ge 2\) ; shift 4 covers both, at cost \(5\ge 4\) . The dual value is \(2\cdot 3+2\cdot 4=14\) .
-
Write the two linear programs of Section 6.5 for the path graph on four nodes \(1,2,3,4\) with edges \(12\) , \(23\) , \(34\) , and give integral optimal solutions of both with equal values.
Answer
Primal: maximize \(x_{12}+x_{23}+x_{34}\) subject to \(x_{12}\le 1\) , \(x_{12}+x_{23}\le 1\) , \(x_{23}+x_{34}\le 1\) , \(x_{34}\le 1\) , \(x\ge 0\) ; optimal solution \(x_{12}=x_{34}=1\) , \(x_{23}=0\) , value \(2\) . Dual: minimize \(y_1+y_2+y_3+y_4\) subject to \(y_1+y_2\ge 1\) , \(y_2+y_3\ge 1\) , \(y_3+y_4\ge 1\) , \(y\ge 0\) ; optimal solution \(y_2=y_3=1\) , value \(2\) .
-
For the cycle on five nodes, show that \(x_e=\tfrac12\) on every edge is a vertex of the matching relaxation \(\{x\ge 0:Mx\le\mathbf 1\}\) by verifying the hypotheses of Theorem 6.1, and compare its value with the maximum matching.
Solution
Let \(M\) be the \(5\times 5\) node–edge incidence matrix of the five-cycle, and \(\bar x\) the vector with every entry \(\tfrac12\) .
Feasibility. Each node lies on two edges, so each row of \(M\bar x\) equals \(\tfrac12+\tfrac12=1\le 1\) , and \(\bar x\ge 0\) .
Active rows. All five rows of \(M\bar x\le\mathbf 1\) hold with equality. By Exercise 6.4 the determinant of \(M\) is \(2\) for \(k=5\) , so the five rows are linearly independent. Here \(n=5\) , the number of edges, so Theorem 6.1 applies: \(\bar x\) is a vertex, the unique solution of \(Mx=\mathbf 1\) .
Comparison. Its objective value is \(5\cdot\tfrac12=\tfrac52\) . A matching in the five-cycle has at most two edges, since three edges would need six distinct endpoints. So the relaxation’s optimum, which is at least \(\tfrac52\) and in fact equal to it because adding the five constraints gives \(2x(E)\le 5\) , exceeds the maximum matching by \(\tfrac12\) . The polytope is not integral, consistent with Corollary 6.10(c): the five-cycle is not bipartite. Rounding the bound down gives \(2\) , the right answer, but only because the objective is integral.
-
The cargo constraints have matrix with rows \((1,2)\) and \((3,2)\) . List all its square submatrices with their determinants, and for each fractional vertex of the cargo polygon identify the determinant whose reciprocal accounts for the denominators.
Answer
The \(1\times 1\) submatrices are the entries \(1\) , \(2\) , \(3\) , \(2\) , and the \(2\times 2\) determinant is \(-4\) . The vertex \((11/3,0)\) comes from the second constraint and \(x_2=0\) , a system whose determinant is \(\pm 3\) , the entry \(3\) . The vertex \((3/2,13/4)\) comes from both constraints, with determinant \(-4\) .
-
Use Corollary 6.8 and the incidence matrix of a directed graph to state a min-max theorem for the following pair: the maximum number of arc-disjoint paths from \(s\) to \(t\) , and the minimum number of arcs meeting all such paths. Say which earlier result you have recovered.
Hint
Give every arc capacity \(1\) . The maximum-flow program has conservation equations with an incidence matrix and bounds \(0\le x\le 1\) , so by Theorem 6.7 it has an integral optimal vertex, a set of arc-disjoint paths after the decomposition used in the proof of Corollary 3.9. Its dual has an integral optimal solution by Corollary 6.8, which is a cut, that is, a set of arcs meeting every path. Equal optimal values give Menger’s theorem for arcs, Corollary 3.9.
-
A minimum-cost flow problem with integer data has one additional constraint \(\sum_{(v,w)}r_{vw}x_{vw}\le R\) limiting total use of a resource. Give a small example, with two parallel paths, in which the relaxation’s unique optimal solution is fractional, and explain which hypothesis of Theorem 6.7 has been lost.
Solution
Send one unit from \(s\) to \(t\) over two parallel arcs. Arc 1 costs \(1\) per unit and uses \(2\) units of the resource per unit of flow; arc 2 costs \(3\) and uses none. The resource limit is \(R=1\) . The problem is
\[ \text{minimize}\quad x_1+3x_2\qquad\text{subject to}\quad x_1+x_2=1,\quad 2x_1\le 1,\quad 0\le x\le 1 . \]The cheap arc is preferred, but the resource constraint allows only \(x_1\le\tfrac12\) . Since the objective equals \(3-2x_1\) on the line \(x_1+x_2=1\) , it is minimized by taking \(x_1\) as large as possible. The unique optimal solution is \(x=(\tfrac12,\tfrac12)\) , with cost \(\tfrac12+\tfrac32=2\) . It is fractional. The integer solutions are \((0,1)\) , with cost \(3\) , and \((1,0)\) , which is infeasible because it uses \(2\) units of the resource.
The flow constraint alone has a totally unimodular matrix, a single row of ones. The added row \((2,0)\) contains the entry \(2\) , so the enlarged matrix has a \(1\times 1\) submatrix with determinant \(2\) and is not totally unimodular. The hypothesis lost is total unimodularity of the constraint matrix; integrality of the right-hand side still holds. Resource-constrained shortest path and flow problems are for this reason genuinely harder than their unconstrained versions.
-
Proposition 6.3 states that an integral polytope is an ideal formulation. Using Chapter 5, explain why the disaggregated facility-location formulation cannot have a totally unimodular constraint matrix in general, citing a specific instance.
Hint
If the matrix were totally unimodular, then with the integer right-hand sides of that formulation every vertex would be integral, by Theorem 6.7, and the relaxation would always attain the integer optimum. Exercise 5.6 gives an instance in which the relaxation’s value is \(3\) and the integer optimum is \(4\) .