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 ∈ Bⁿ by

   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

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

2. The nonnegative integer variables x ∈ ℤ⁴ satisfy the linear equality

   (1)

   1. (7 points) Give a linear inequality of the form g₂x₂ + g₃x₃ + g₄x₄ ≥ 1 that must be satisfied by {x₂,x₃,x₄} if x₁ ≤ 2.
   2. (8 points) Give a linear inequality of the form h₂x₂ + h₃x₃ + h₄x₄ ≥ 1 that must be satisfied by {x₂,x₃,x₄} if x₁ ≥ 3.
   3. (5 points) Argue why the inequality

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

   4. We can define a new variable y₁ so that

      (2)

      1. (5 points) Show that y₁ must be integral.
      2. (10 points) Derive another valid inequality on x₂, x₃, and x₄, using the disjunction that either y₁ ≤ 0 or y₁ ≥ 1, as in parts 2a–2c. Which valid inequality is stronger?
3. In this problem, we consider two problems in :

   The partition problem: Given n positive integers {a₁,…,a_n} with sum ∑ _j=1ⁿa _j even, does there exist a subset J ⊆{1,…,n} such that

   

   2-machine scheduling: Given two identical machines, m jobs requiring positive integer processing time b_j 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 -Complete. Can we conclude that the partition problem is -Complete?
   3. (5 points) Assume the partition problem is -Complete. Can we conclude that the 2-machine scheduling problem is -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 C₁,…,C_k each containing exactly p items. We can represent the assignment of items to clusters using a n × k matrix Y with

   Let e^q represent the q-dimensional vector of ones.

   1. (10 points) Show that Y e^k = eⁿ and Y ^T eⁿ = pe^k.
   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 Xeⁿ?