Combinatorial Optimization and Integer Programming
Spring 2015

Midterm Exam, Friday, April 24, 2015.

Please do all four problems. Show all work. No books or calculators allowed. You may use any result from class, the homeworks, or the texts, except where stated. You may use one sheet of handwritten notes. The exam lasts 110 minutes.

  1. We want to find a maximum weighted clique on the graph G = (V,E). Let n = |V |. We define binary variables x Bn by
        1   if vertex v is in the clique
xv =    0   otherwise

    and we denote the set of feasible vectors x by S.

    1. (10 points) Show that dim(S) = n.
    2. (10 points) An independent subset U V is a collection of vertices, no two of which are adjacent in G. Any clique contains at most one of the vertices in U. Show that the corresponding inequality
    xv ≤ 1

      defines a facet of the convex hull of S if U is a maximal independent set.

  2. The nonnegative integer variables x 4 satisfy the linear equality
    x1 + 1.6x2 - 2.7x3 + 0.1x4 =  2.5.

    1. (7 points) Give a linear inequality of the form g2x2 + g3x3 + g4x4 1 that must be satisfied by {x2,x3,x4} if x1 2.
    2. (8 points) Give a linear inequality of the form h2x2 + h3x3 + h4x4 1 that must be satisfied by {x2,x3,x4} if x1 3.
    3. (5 points) Argue why the inequality
      max {g ,h  }x  + max {g ,h  }x +  max {g ,h  }x  ≥ 1
       2  2  2          3  3  3         4   4  4

      is valid for any nonnegative integer solution to (1). Write down the inequality.

    4. We can define a new variable y1 so that
      y1 - 0.4x2 + 0.3x3 + 0.1x4 =  0.5.

      1. (5 points) Show that y1 must be integral.
      2. (10 points) Derive another valid inequality on x2, x3, and x4, using the disjunction that either y1 0 or y1 1, as in parts 2a2c. Which valid inequality is stronger?
  3. In this problem, we consider two problems in NP:

    The partition problem: Given n positive integers {a1,,an} with sum j=1na j even, does there exist a subset J ⊆{1,,n} such that

    ∑        ∑
    aj =     aj?
j∈J       j⁄∈J

    2-machine scheduling: Given two identical machines, m jobs requiring positive integer processing time bj for j = 1,,m, and a positive integer T, can the jobs be scheduled so that all the jobs are finished by time T? Note that each job must be processed on exactly one machine, each machine can only process one job at a time, once a job is started it must be run to completion, and the jobs can be processed in any order.

    1. (10 points) Show that any instance of the partition problem can be polynomially transformed into an equivalent instance of the 2-machine scheduling problem.
    2. (5 points) Assume the 2-machine scheduling problem is NP-Complete. Can we conclude that the partition problem is NP-Complete?
    3. (5 points) Assume the partition problem is NP-Complete. Can we conclude that the 2-machine scheduling problem is NP-Complete?
  4. Let k 2 and p 2 be positive integers. Assume we have n = kp items. We want to cluster the items into k clusters C1,,Ck each containing exactly p items. We can represent the assignment of items to clusters using a n × k matrix Y with
          {  1  if item  i is in cluster C
Yir =                             r
         0  otherwise.

    Let eq represent the q-dimensional vector of ones.

    1. (10 points) Show that Y ek = en and Y T en = pek.
    2. To set up a semidefinite programming relaxation of the clustering problem, we can define an n × n matrix X = Y Y T .
      1. (10 points) Show each diagonal entry of X is equal to one.
      2. (5 points) What is the value of the product Xen?