MATP6620 / ISYE6760
Integer and Combinatorial Optimization
Due: Thursday, April 15, 2021.
Penalty for late homeworks: 10% for each day or part of a day.
Given a feasible solution to the partitioning problem, define the n × k matrix Y with
and set X = Y Y T , so X ≽ 0. Note that
since each vertex is in exactly one set. Further,
Thus, X is feasible in the given SDP.
Now we examine the objective function value. We have
and so the objective function value is equal to the value of the partition. Hence the SDP is a relaxation of the partition problem.
where λmax(A) and λmin(A) denote the largest and smallest eigenvalues of A respectively. Assume E≠∅. Prove
Since E≠∅, the adjacency matrix is nonzero. Let w denote the vector of ones, and then wT Aw > 0, so A has at least one positive eigenvalue.
All the diagonal entries of A are zero, so trace(A) = 0, so the sum of the eigenvalues of A is zero. Therefore, A has at least one negative eigenvalue.
Thus, λmax(A) > 0 > λmin(A).
Let m1 be the number of vertices in V 1 and let m2 denote the number of vertices in V 2. Then the adjacency matrix is
The rank of the matrix A is 2, as can be seen by Gaussian elimination, so A has 2 nonzero eigenvalues. Consider the vector u = (α,…,α,β,…,β)T , consisting of m 1 α terms and m2 β terms. We claim u is an eigenvector of A for appropriately chosen values of α and β. In fact, we have
This is equal to λu if
which holds if
Hence the Hoffman bound is
Alternatively, for any bipartite graph, we have an adjacency matrix with the structure
Assume (u,v) is an eigenvector of A with eigenvalue λ. Then
Notice that we then have
so -λ is also an eigenvalue of A. It follows that λmin(A) = -λmax(A), so the bound is 2.
For a bipartite graph, we have a coloring using just 2 colors: the vertices in V 1 have one color and the vertices in V 2 have a different color. Thus, the coloring nunber is 2, equal to the Hoffman bound.
Assume X is symmetric. Assume the 2 × 2 submatrices
are positive semidefinite. Show that x13 can be chosen so that X is positive semidefinite. (This result can be generalized to allow an approach to solving semidefinite programs that exploits sparsity. The approach involves looking at cliques in chordal graphs.)
We need to be able to choose x13 so that the following (sub)determinants are nonnegative:
We break into cases based on the value of x22, which must be nonnegative:
With this choice, we get
since the given 2 × 2 submatrices are positive semidefinite.
With this choice, we also get
since x11x22 ≥ x122 ≥ 0 and x 22x33 ≥ x232 ≥ 0.
Thus, we can always choose x13 to ensure X ≽ 0.
Use it to solve the Lovász theta relaxation of some randomly generated node packing problems using the routine lovaszthetarand.m
You need to select 2 parameters in matlab: the matrix size msize, and density which controls the number of edges in the graph. The expected number of edges is
For a version of the code for solving non-random instances, see lovasztheta.m and an example file edges8.mat