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.

- Given a complete graph G = (V,E) with edge weights w
_{e}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 w_{ii}= 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 with

and set

=^{T }, so ≽ 0. Note thatsince each vertex is in exactly one set. Further,

Thus,

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.

- 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≠∅. ProveSolution:

Since E≠∅, the adjacency matrix is nonzero. Let w denote the vector of ones, and then w

^{T }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). - 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 m

_{1}be the number of vertices in V_{1}and let m_{2}denote the number of vertices in V_{2}. Then the adjacency matrix isThe 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 m_{2}β terms. We claim u is an eigenvector of A for appropriately chosen values of α and β. In fact, we haveThis 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. - Let
Assume X is symmetric. Assume the 2 × 2 submatrices

are positive semidefinite. Show that x

_{13}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 x

_{13}so that the following (sub)determinants are nonnegative:and

We break into cases based on the value of x

_{22}, which must be nonnegative:- If x
_{22}= 0: Then we must have x_{12}= x_{23}= 0 for the subdeterminants of the given two 2 × 2 matrices to be nonnegative. We can then choose x_{13}= 0 and we get X ≽ 0. - If x
_{22}> 0: The determinant of X is a concave quadratic function of x_{13}. We choose x_{13}to maximize det(X). It is maximized whenWith this choice, we get

since the given 2 × 2 submatrices are positive semidefinite.

With this choice, we also get

since x

_{11}x_{22}≥ x_{12}^{2}≥ 0 and x_{ 22}x_{33}≥ x_{23}^{2}≥ 0.

Thus, we can always choose x

_{13}to ensure X ≽ 0. - If x
- 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

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