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:
                   ∑n   ∑n
min        0.5   i=1   j=1 wijXij
subject to                   Xii  =   1   i = 1, ...,n
                             Xe   =   pe
                              X       symmetric   and positive semide finite

    Solution:

    Given a feasible solution to the partitioning problem, define the n × k matrix Y with

          {
Yij =   1  if vertex i is in set j
        0  otherwise

    and set X = Y Y T , so X 0. Note that

          ∑k
Xii =     Yi2j = 1
      j=1

    since each vertex is in exactly one set. Further,

                                               (       )
(   )     ∑n        ∑n  ∑k          ∑k       ∑n           ∑k
 Xe  i =      Xil =        Yij Ylj =    Yij     Ylj   = p    Yij = p
          l=1       l=1 j=1         j=1      l=1           j=1

    Thus, X is feasible in the given SDP.

    Now we examine the objective function value. We have

       ∑n  ∑n              ∑n  ∑n     ( ∑k      )
0.5        wij Xij = 0.5      wij      YilYjl
   i=1 j=1             i=1 j=1
                                    l=1

    Note that

    ∑ k          {
    YilYjl =    1  if i and j are in the same set
 l=1            0  otherwise

    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
            λmax (A)
χ ≥ 1 - --------
         λmin(A)

    where λmax(A) and λmin(A) denote the largest and smallest eigenvalues of A respectively. Assume E. Prove

    λmax(A ) > 0 > λmin(A).

    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

          ⌊                         ⌋
        0  ......  0  1  ...  1
      | ..           ..  ..      .. |
      || .           .  .      . ||
      || ...           ...  ...      ... ||
A  =  | 0  ......  0  1  ...  1 |
      ||                         ||
      || 1  ......  1  0  ...  0 ||
      ⌈ ...           ...  ...      ... ⌉

        1  ......  1  0  ...  0

    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

          ⌊                          ⌋
         0  ......  0  1  ... 1    ⌊    ⌋    ⌊  m β  ⌋
      |  ..          ..  ..       .. |   α           2.
      ||  .          .  .       . || |  .. |    ||   ..   ||
      |  ...          ...  ...       ... | ||  . ||    ||  m2β  ||
Au =  ||                          || | α  | =  | m  α  |
      ||  0  ......  0  1  ... 1  || || β  ||    ||   1.   ||
      |  1  ......  1  0  ... 0  | |⌈  .. |⌉    ||   ..   ||
      |⌈  ..          ..  ..       .. |⌉    .      ⌈ m1 α  ⌉
         .          .  .       .     β
         1  ......  1  0  ... 0

    This is equal to λu if

    λα = m2 β   and   λβ = m1 α,

    which holds if

    α      ∘ -m--                √ ------
--=      --2  with   λ =     m1m2.
β         m1

    Hence the Hoffman bound is

             √ ------
        ---m1m2---
χ ≥ 1 - - √m---m-- = 2.
              1  2

    Alternatively, for any bipartite graph, we have an adjacency matrix with the structure

         [          ]
A =    0     M    .
       M  T  0

    Assume (u,v) is an eigenvector of A with eigenvalue λ. Then

    M v = λu     and      M Tu = λv.

    Notice that we then have

      [   u ]    [ 0     M  ] [   u ]    [ - M v ]    [  - λu ]        [   u ]
A         =      T                =       T     =           =  - λ
    - v        M     0      - v         M  u          λv             - v

    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
          ⌊ x11  x12  x13 ⌋
      ⌈               ⌉
X  =    x21  x22  x23   .
        x31  x32  x33

    Assume X is symmetric. Assume the 2 × 2 submatrices

    [          ]          [          ]
  x11  x12     and      x22  x23
  x21  x22              x32  x33

    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:

    |         |
| x11  x13|
||         || =  x11x33 - x213 ≥ 0
  x13  x33

    and

    |              |
| x11  x12 x13 |
|| x    x   x   || =  x  x  x  + 2x  x  x   - x  x2  - x  x2 -  x  x2 ≥  0.
||  21   22   23||     11 22 33     12  23  13    11 23    33 12    22 13
  x31  x32 x33

    We break into cases based on the value of x22, which must be nonnegative:

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

                        (        )
          density     msize
E (E ) = -----------      2       for 0 ≤ density ≤  1.
        1 + density

    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