Name: |

MATP6620/ISYE6770

Combinatorial Optimization and Integer Programming

Spring 2013

Midterm Exam, Friday, April 19, 2013.

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.

- (30 points; each part is worth 10 points)
- The binary variables x
_{1}, x_{2}, x_{3}, x_{4}, and x_{5}must satisfy the knapsack constraint(1) Show that the valid cover inequality

has Chvatal rank equal to one. (Note: You will need to use the valid inequalities x

_{i}≤ 1 in your derivation.) - The binary variables x
_{i}, i = 1,…,n must satisfy the knapsack constraint(2) where b and a

_{i}, i = 1,…,n are positive scalars. Assume b > a_{i}for i = 1,…,n. Assume further that there exists a subset J ⊆{1,…,n} with(3) - Give a valid cover inequality constraint.
- Show that your cover inequality has Chvatal rank equal to one.

- The binary variables x
- (20 points)
The Node Packing and Max Clique feasibility problems can be described as follows:

Node Packing: Given a graph G = (V,E) and a integer k, does there exist a subset U ⊆ V with ∣ U∣ ≥ k where no two of the vertices in U share an edge?

Max Clique: Given a graph G = (V,E) and an integer p, does there exist a clique W ⊆ V with with ∣ W∣ ≥ p?Using the fact that Node Packing is NP-Complete, show that the Max Clique problem is NP-complete.

- (30 points; each part is worth 10 points)
- Assume the nonnegative scalar integer variable y and the nonnegative scalar continuous
variable x satisfy the inequality
(4) where b is a non-integral scalar parameter. Let f be the fractional part of b, so b = ⌊b⌋ + f and 0 < f < 1. Prove that the inequality

(5) is valid.

- The optimal solution of the LP relaxation of the mixed integer program
is x

_{1}= x_{2}= 0, y_{1}= 2.5, y_{2}= 1.2.- Give three valid inequalities of the type in part 3a that are violated by the solution to the LP relaxation.
- Show that none of your inequalities is implied by the other two.

- Assume the nonnegative scalar integer variable y and the nonnegative scalar continuous
variable x satisfy the inequality
- (20 points)
Show that the shortest Hamiltonian cycle in the following graph has length 50. Make sure to prove your solution is optimal.