MATP6620/ISYE6770

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.

- We want to find a maximum weighted clique on the graph G = (V,E). Let n = |V |. We
define binary variables x ∈ B
^{n}byand we denote the set of feasible vectors x by S.

- (10 points) Show that dim(S) = n.
- (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.

- The nonnegative integer variables x ∈ ℤ
^{4}satisfy the linear equality(1) - (7 points) Give a linear inequality of the form g
_{2}x_{2}+ g_{3}x_{3}+ g_{4}x_{4}≥ 1 that must be satisfied by {x_{2},x_{3},x_{4}} if x_{1}≤ 2. - (8 points) Give a linear inequality of the form h
_{2}x_{2}+ h_{3}x_{3}+ h_{4}x_{4}≥ 1 that must be satisfied by {x_{2},x_{3},x_{4}} if x_{1}≥ 3. - (5 points) Argue why the inequality
is valid for any nonnegative integer solution to (1). Write down the inequality.

- We can define a new variable y
_{1}so that(2)

- (7 points) Give a linear inequality of the form g
- In this problem, we consider two problems in :
The partition problem: Given n positive integers {a

_{1},…,a_{n}} with sum ∑_{j=1}^{n}a_{ j}even, does there exist a subset J ⊆{1,…,n} such that2-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.- (10 points) Show that any instance of the partition problem can be polynomially transformed into an equivalent instance of the 2-machine scheduling problem.
- (5 points) Assume the 2-machine scheduling problem is -Complete. Can we conclude that the partition problem is -Complete?
- (5 points) Assume the partition problem is -Complete. Can we conclude that the 2-machine scheduling problem is -Complete?

- 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
_{1},…,C_{k}each containing exactly p items. We can represent the assignment of items to clusters using a n × k matrix Y withLet e

^{q}represent the q-dimensional vector of ones.- (10 points) Show that Y e
^{k}= e^{n}and Y^{T }e^{n}= pe^{k}. - To set up a semidefinite programming relaxation of the clustering problem, we can
define an n × n matrix X = Y Y
^{T }.- (10 points) Show each diagonal entry of X is equal to one.
- (5 points) What is the value of the product Xe
^{n}?

- (10 points) Show that Y e