Week 6
Integral Polyhedra
We have seen some examples1 of linear programming formulation that are integral, meaning that every basic feasible solution is an in- tegral vector. This week we develop a theory of integral polyhedra that explains the integrality of these example by a simple property of the constraint matrix of these programs.
1 We have proved this for maximum weight bipartite matching, minimum vertex cover, and the minimum cut problems.
6.1 Totally Unimodular Matrices Consider the integer program
minimize subject to
c · x
Ax = b
x ∈ Z n+
(IP)
(LP)
must a basic feasible solution x that is optimal. Let B be a basis defining x. Then xB = A−1b, while all non-basic variables must be
B
0. It follows that if A−1 is an integral matrix then x must be integral B
as well. It turns out, as we shall prove shortly, that a sufficient condition for the integrality of A−1 is det(AB) ∈ {1, −1}. This
B
motivates the following definition.
Definition 6.1. We say a matrix A ∈ Zm×n with full row rank is unimodular if the determinant of each basis of A is 1 or −1.
First we will show that if the program (LP) is alway integral whenever A is unimodular, and that a weaker form of the converse also holds.
whereA∈Zm×n andb∈Zm.
We would like to know what are the properties that A and b
must have such that the linear relaxation minimize c · x
subject to Ax = b x≥0
always has an integral solution.
Recall that if the linear program has bounded objective, there
© Copyright 2021 Julián Mestre.
This work is licensed under a Creative Commons Attribution-NonCommercial- ShareAlike 4.0 International License.
week 6 – integral polyhedra
discrete optimization 2
Theorem 6.1. A full row rank matrix A ∈ Zm×n is unimodular if and only if the polyhedron {x ∈ Rn : Ax = b,x ≥ 0} is integral for all b ∈ Zm.
Proof. We first prove the forward direction. Let x be an extreme
pointandBbeabasisofx. Ourgoalistoshowthatxisinte-
gral. From Cramer ’s rule2 we know that A−1 = Adj(AB ) , where B det(AB )
Adj(AB ) is the adjugate3 , 4 of AB . Since AB is integral, it follows thatAdj(A )mustbeintegralaswell.Togetherwiththefactthat
det(AB) ∈ {1, −1}, this implies the integrality of A−1 and, therefore, B
that of x.
The backward direction is surprisingly easy. Let B be a basis of
A. Our goal is to show that |det(A )| = 1. Let b = A z+e where BBi
ei is the unit vector with a single 1 in its ith coordinate and zeros elsewhere, i is an arbitrary index in {1, . . . m}, and z is a suitable integral vector such that
xB = A−1b = z + A−1ei ≥ 0. BB
Cramer ’s rule, Wikipedia.
3 Adjugate matrix, Wikipedia.
4 The exact definition of the adjugate of a matrix is not important. The only thing you need to know is that the entries of the adjugate are defined in terms of determinants of submatrices of the orginal matrix.
Just for completeness, the adjugate of AB is defined as the transpose of its cofactor matrix,
Adj(AB) = CT ,
where cij is the (i,j)-cofactor of AB, which is defined a (−1)i+j times the determinant of the submatrix of AB that results from removing its ith row and its jth column.
This ensures that the basic solution induced by B is feasible. Since (LP) is integral it follows that the ith column of of A−1 must be
B
integral. Because i is arbitrary, it follows that every column of A−1
B
This theorem can be generalized to linear programs that are not in standard form by refining the the property we require from the constraint matrix.
Definition 6.2. We say a matrix A is totally unimodular if every square submatrix of A has determinate 0, 1, or −1.
Theorem 6.2. A matrix A ∈ Zm×n is totally unimodular if and only if thepolyhedron{x∈Rn :Ax≤b,x≥0}isintegralforallb∈Zm.
Proof sketch. For simplicity, here we assume b ≥ 0, but a similar argument holds for general b ∈ Zm.
The forward direction is similar as Theorem 6.1. For the other di- rection, it suffices to argue that A is totally unimodular if and only if A I is unimodular, and that the extreme points of the polyhe- dron{x∈Rn :Ax≤b,x≥0}areintegralifandonlyiftheextreme points of the polyhedron (x,z) ∈ Rn+m : Ax+z = b,x ≥ 0,z ≥ 0 are integral.
Now that we have established the importance of these matrices, we shall explore some of their properties and alternative ways of proving that a given matrix is totally unimodular.
is integral. Therefore it must be that det(AB) and det(A−1) are B
integral. Together with the relation
det(AB) det(A−1) = 1,
B
we conclude that | det(AB)| = | det(A−1)| = 1. B
2
B
Here are some example to clarify our definitions so far.
The following matrix is unimodular
1 0 −1 011,
but the following matrix is not
1 −1 1 1 0 −1.
The following matrix is totally unimodular
1 0 −1 0 1 1, 1 0 −1
but the following matrix is not
since det
1 −1 1 1 0 −1 101
1 1
1 −1 = −2.
week 6 – integral polyhedra
discrete optimization 3
6.2 Properties of Totally Unimodular Matrices
Let A be a totally unimodular matrix. There are a few observations
we can make about these matrices:
i) The entries of A must be either 0, 1, or −1.
ii) The transpose of A is also totally unimodular. A
iii) The matrix I is also totally unimodular. A
iv) The matrix −A is also totally unimodular.
A neat corollary5 of the these properties is that if A is totally
unimodular then the polyhedron
x∈Rn :a≤Ax≤b,l≤x≤u
is integral for all integral vector a, b, l, and u.
Another corollary is that if c and b are integral and A is totally
unimodular then both the primal program min {c · x : Ax ≥ b, x ≥ 0} and the dual program maxb·y : ATy ≤ c,y ≥ 0 are integral.
6.3 Alternative Characterization
While Definition 6.2 is well suited to prove the integrality of the polyhedron associated with a constraint matrix A, it is not always straightforward to prove that a particular matrix A is totally uni- modular. In this section we introduce an alternative characteriza- tion of totally unimodular matrices that is easier to work with.
A bi-coloring of a matrix M is a partition of its columns into red and blue columns. We say the bi-coloring equitable if for every row of M the sum of its red entries differs from the sum of its blue entries by at most 1.
Theorem 6.3. A matrix A is totally unimodular if and only every column-induced submatrix of A admits an equitable bi-coloring.
The proof of this theorem is beyond the scope of this class. Here we will just make use of the theorem to prove that certain matrices are totally unimodular.
Lemma 6.1. The constraint matrix associated with the bipartite matching problem polyhedron
|E| x∈R+ : e∈δ(u)xe ≤1∀u∈V
is totally unimodular.
Proof. Let A be the constraint matrix associated with the polyhe- dron. Each row of A is associated with a vertex u in our bipartite
5 This corollary is a bit surprising. It means that if P ⊆ Rn+ is a polyhedron defined by a totally unimodular matrix, and Q = [l1,u1]×···×[ln,un] then P ∩ Q is also an integral. In general, this is not the case.
+
Notice that because A is totally uni- modular if and only if AT is totally unimodular, we have the equivalent condition that any row induced sub- matrix of A admits a row bi-coloring such that for every column the sum of the red entries differs from the sum of the blue entries by at most 1.
week 6 – integral polyhedra
discrete optimization 4
graph. If u is in the left shore of the graph, then we color the cor- responding row red. If u is in the right shore of the graph, then we color the corresponding row blue.
Each column of A is associated with an edge (u, v) ∈ E, and
it has a 1 in each of the rows associated with u and v, and 0 else- where. It is easy to see that the bi-coloring is equitable for all row induced matrices of M. Therefore the matrix is totally unimodu- lar.
Lemma 6.2. The constraint matrix associated with the circulation prob- lem polyhedron
|E| f∈R+ : e∈δin(u)fe = e∈δout(u)fe ∀u∈V
is totally unimodular.
Proof. Let A be the constraint matrix associated with the polyhe- dron. Each row of A is associated with a vertex u ∈ V. We color red all rows. Each column of A is associated with an edge (u, v) ∈ E, and has a −1 in the row associated with u and a 1 in the row asso- ciated with v, and 0 elsewhere. It is easy to see that the bi-coloring is equitable for all row induced matrices of M. Therefore the matrix is totally unimodular.
6.4 Subset Systems
We now turn our attention to a broad class of subset selection prob- lems. These problems are defined by a pair (U, I ), where U is a uni- versal set of elements and I ⊆ 2U is a collection of feasible6 subsets of U. The pair (U,I) is called a subset system if for any S ⊂ T ⊆ U it holdsthatT ∈I impliesS∈I.
Given a cost function c : U → R+, the canonical optimization problem associated with (U,I) is
To get a formulation for the maximum s-t flow problem we just need to add the edge capacity constraints, which do not affect the total unimodularity of the constraint matrix, and maximize the linear objective fts .
Furthermore, since the transpose
of the resulting matrix is also totally unimodular, it follows that the dual
is also integral, which, as we saw last week, corresponds to the minimum s-t cut problem.
maximize
subject to
c(S) S ∈ I
6 In the optimization literature fea- sible sets are some times also called independent sets. Originally, a par- ticular type of subset system was developed as an abstraction of linear independence:
U = collection of vectors, and
Many natural problems7 fit under this framework. Some of them are hard and some, easy. We would like to identify the properties of I that make the corresponding optimization problem easy.
Definition 6.3. The rank function r : 2U → Z+ of the system (U, I ) is defined as follows
r(S)= max |T|. T ⊆S:T ∈I
It is easy to show that the following is an integer formulation for the canonical problem.
7 For example, maximum weight spanning tree, maximum matching, and maximum weight independent set in graphs.
maximize subjectto
j∈U cjxj
x ≤r(S) ∀S⊆U
(IP-IS)
j∈S j
xj ∈{0,1} ∀j∈U
I =
S⊆U:vectorsinSare . linearly independent
week 6 – integral polyhedra
discrete optimization 5
As we shall prove shortly, the following property is key in argu- ing that the linear relaxation of (IP-IS) is integral.
Definition 6.4. The subset system (U, I ) is called a matroid if for any two subsets S,T ∈ I such that |S| < |T| the following is true
The matroid exchange axiom:
∃x∈T\S : S+x∈I
Equation 6.1 is referred to as the matroid exchange axiom.
(6.1)
x T
S
|S| < |T|
Theorem 6.4. Let (U, I ) be a matroid, then the following polyhedron is
Not every problem has the matroid exchange property. For example, consider the subset system (U,I) definedbythematchingproblemon the following graph
∈T ∈T ∈S
BothS,T ∈Iand|S|<|T|butitisnot possible to add an edge from T \S to S and remain feasible.
integral
|U| x∈R+ :x(S)≤r(S)∀S⊆U .
Proof. Let x be a vertex of the polyhedron. Our goal is to show that x is integral. Let c be the cost vector that make x the unique optimal solution of the linear program
The dual program is given by
and
cj −cj+1
yS = c|U| 0
maximize subjectto
j∈U cjxj
x ≤r(S) ∀S⊆U
j∈S j
xj ≥0 ∀j∈U
minimize S⊆U r(S) yS
subjectto y ≥c ∀j∈U
S:j∈S S j
yS ≥0 ∀S⊆U
Let us re-number the elements of our universal set U = {1, . . . , |U|} so that cj ≥ cj+1 for j = 1,...,|U|−1. We define a sequence of sets ∅=S(0) ⊂S(1) ⊂···⊂S(|U|) =Uasfollows
S(j) = {1,...,j} for j = 0,...,|U|.
Based on these sets we create a pair of primal and dual solutions
xj = r(S(j))−r(S(j−1)) for j = 1,...,|U|,
S = S(j) and j = 0,...,|U|−1, S = S(|U|),
otherwise.
To show that x is integral, we will argue that x = x. We will do this by proving the following properties:
i) j∈U cjxj = S⊆U r(S)yS
ii) y is a feasible solution for the dual program
iii) x is a feasible solution for the primal program
These properties imply that x is optimal, and since there is a unique optimal x = x. It is clear that x is integral, so the theorem follows.
week 6 – integral polyhedra
discrete optimization 6
Let us start with the first property
j∈U
|U|
(j)
(j−1)
cjxj = =
cj r(S |U|−1
)−r(S (j)
)
j=1
(|U|) ) + c|U|r(S
j=1 |U|
(cj − cj+1)r(S (j)
)
= yS(j)r(S ) j=1
yS r(S)
For the second property we note that for all j ∈ U
|U| |U|−1
S:j∈S
i=j
=
S⊆U
yS(i) = (ci −ci+1)+c|U| = cj. i=j
yS =
For the third property we let S be an arbitrary subset of U.
Choose T to be a maximum cardinality feasible subset of S, and setR = j∈S:xj =1. Wewouldliketotoarguethat|R| ≤ |T|. For the sake of contradiction, suppose that was not the case. Then, by the matroid exchange axiom (6.1), we know that there exists j∈R\T ⊆SsuchthatT+j∈I,contradictingthefactthatTisa maximum cardinality feasible subset of S.
Exercises
1. Argue that the matrix A is totally unimodular if and only if A I is unimodular.
2. Let A ∈ Zm×n and b ∈ Zm+ . Argue that the polyhedron
{x ∈ Rn : Ax ≤ b,x ≥ 0} is integral if and only if the polyhedron (x,z) ∈ Rn+m : Ax+z = b,x ≥ 0,z ≥ 0 is integral.
3. Let I1, . . . , In be a collection of open intervals of the real line. Each interval I has associated a profit p(I). The objective is to pick a maximum profit subset of intervals such that no two intervals overlap.
Consider the following program:
This is not a proper integer linear program, as it contains an infinite number of constraint. Show that there is a set Q of cardi- nality2n−1suchthatforanyq ∈ Rthereisp ∈ Qsuchthatthe constraints generated by p and q are equivalent.
maximize I p(I)xI subjectto x ≤1
∀p∈R
∀ I = I1,...,In
I:p∈I I
xI ∈ {0,1}
Notice that we have not used anything about the subset system to prove the first and the second properties.
For the last property we need to make use the matroid exchange axiom.
week 6 – integral polyhedra
discrete optimization 7
Then show that the linear relaxation
has a totally unimodular constraint matrix.
4. Prove that the subset system associated with the interval selec- tion problem described in the previous exercise does not have the matroid property.
5. Let r be the rank function of a matroid (U, I ). Prove that for any S, T ⊆ U we must have
r(S∩T)+r(S∪T) ≤ r(S)+r(T).
6. Let (U, I ) be the subset system defined by a set of vector U and the collection of linearly independent subsets of U. Prove that the system is a matroid.
7. Let (U, I ) be a matroid and r be its rank function. Argue that the following linear program8 is integral.
maximize I p(I)xI subjectto x ≤1
∀p∈Q
∀ I = I1,...,In
minimize
j∈U cjxj
x(S) ≤ r(S) x(U) = r(U) xj ≥ 0
8 Notice that for a matroid whose fea- sible sets correspond to acyclic subset of edges, the program corresponds to finding a minimum weight spanning tree.
I:p∈I I
xI ∈ [0,1]
∀S ⊆ U
week 6 – integral polyhedra
discrete optimization 8
Solutions of selected exercises
1. We show that that for every square submatrix of A there is a
column-induced submatrix of A I having the same determinant up to a sign change.
Let M be the square submatrix of A induced by the rows R ⊆ {1,...,m} and the columns C ⊆ {1,...,n}. Let T be the the column- induced submatrix of A I defined by the columns of A indexed by C and the columns of I indexed by {1,...,m}\R. Notice that the relation is reversible—starting from T, we can construct M.
At this point, it should be easy to see that det(M) = ± det(T ). Indeed, we can compute det(T) by first expanding the determinant along the columns that come from I until we are left with M.
It follows that the determinant of every square submatrix of A is in {−1, 0, 1} if and only if the determinant of every column-induced submatrix of A I is in {−1, 0, 1}.
2. We establish a one-to-one integrality-preserving correspondence between the extreme points of the two polyhedra. Let us denote the two polyhedra with P1 and P2 respectively.
Letx ∈ Rn andz = b−Ax. Clearly,x ∈ P1 ifandonlyif
(x, z) ∈ P2. Furthermore, because A and b are integral, we know that x is integral if and only if (x, z) is integral. It only remains to how that x is a basic feasible solution of P1 if and only if (x, z) is a feasible solution of P2.
Suppose x is a basic feasible solution of P1. Consider a maximal set of linearly independent tight constraints at x. Let R ⊆ {1, . . . , m} be the indices of these constraints than come from the systems
Ax ≤ b and C ⊆ {1,...,n} be the indices of these constraints that come from x ≥ 0. Recall that because x is basic, we know that it is the only solution that meets those constraints with equality.
Now consider the basis B of P2 formed by taking the columns of I indexed by {1,...,m} \ R and the columns of A indexed by {1,...,n} \ C . It is not hard to see that (x,z) is the basic feasible solution induced by the basis B.
Using a similar argument, we can justify the reverse direction: If (x, z) is a basic feasible solution of P2 then x must be a basic feasible solution of P1.