MATP6620 / ISYE6760
Integer and Combinatorial Optimization

Homework 5.
Solutions

Due: Thursday, April 15, 2021.
Penalty for late homeworks: 10% for each day or part of a day.

1. Given a complete graph G = (V,E) with edge weights we and n = kp nodes, we wish to partition the vertices into k sets each containing exactly p vertices so as to minimize the sum of the edge weights of the edges with endpoints in the same set. Let e denote the n-vector of ones and let wii = 0 for i = 1,,n. Show that the following semidefinite program gives a lower bound on the optimal value of this problem, where X is an n × n matrix: Solution:

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 Note that and so the objective function value is equal to the value of the partition. Hence the SDP is a relaxation of the partition problem.

2. The coloring number χ of an undirected graph G = (V,E) is the smallest number of colors needed to color the vertices V so that no two adjacent vertices share a color. Let n = |V | and let A denote the n × n adjacency matrix. The Hoffman bound on χ is where λmax(A) and λmin(A) denote the largest and smallest eigenvalues of A respectively. Assume E. Prove Solution:

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).

3. Recall the Hoffman bound from Question 2. Show the bound is tight if G is a complete bipartite graph with E. (In a complete bipartite graph, V can be partitioned into two sets V 1 and V 2, every vertex in V 1 is adjacent to every vertex in V 2, no vertex in V 1 is adjacent to any other vertex in V 1, and no vertex in V 2 is adjacent to any other vertex in V 2.)

Solution:

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.

4. Let 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.)

Solution:

We need to be able to choose x13 so that the following (sub)determinants are nonnegative: and We break into cases based on the value of x22, which must be nonnegative:

• If x22 = 0: Then we must have x12 = x23 = 0 for the subdeterminants of the given two 2 × 2 matrices to be nonnegative. We can then choose x13 = 0 and we get X 0.
• If x22 > 0: The determinant of X is a concave quadratic function of x13. We choose x13 to maximize det(X). It is maximized when 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.

5. The package cvx is a modeling framework for convex optimization problems that works within matlab. Install cvx, available from http://cvxr.com/cvx/download/

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

6. Give a progress report on your project. Your report should be at least a couple of paragraphs long. It doesn’t need to repeat anything from your initial report from Homework 3.
 John Mitchell Amos Eaton 325 x6915. mitchj at rpi dot edu Office hours: Monday and Thursday 1pm–2pm. webex: https://rensselaer.webex.com/meet/mitchj