Name: |

MATP6620/ISYE6770

Combinatorial Optimization and Integer Programming

Spring 2011

Midterm Exam, Tuesday, April 19, 2011.

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.

Q1 | /20 | |

Q2 | /20 | |

Q3 | /20 | |

Q4 | /40 | |

Total | /100 |

- (20 points; each part is worth 10 points)
- The binary variables x
_{1}, x_{2}, x_{3}, and x_{4}must satisfy the constraintFind a minimal cover inequality. Lift the cover inequality.

- The binary variables z
_{1}, z_{2}, z_{3}, and z_{4}must satisfy the constraintUse the results of part (a) to derive an inequality that defines a facet of the set of z IB

^{4}satisfying the constraint. Why is your constraint facet-defining?

- The binary variables x
- (20 points)
The linearly dependent vectors x

^{1},…,x^{m}in IR^{n}are all on the hyperplane a^{T }x = b, where b≠0. Show that they are affinely dependent. - (20 points)
Let G = (V,E) be a graph with nonnegative edge weights w

_{e}.- (15 points) Show that the problem of finding the maximum weight matching
on G is equivalent to finding a maximum weight perfect matching on another
graph G′ = (V ′,E′) with nonnegative edge weights w
_{e}′, where V ′ and E′ are obtained from V and E by adding certain vertices and edges. - (5 points) Given a maximum weight perfect matching problem, how can you construct an equivalent minimum weight perfect matching problem with nonnegative edge weights?

- (15 points) Show that the problem of finding the maximum weight matching
on G is equivalent to finding a maximum weight perfect matching on another
graph G′ = (V ′,E′) with nonnegative edge weights w
- (40 points; 6 parts on 3 pages)
This question is concerned with node packings in the following graph.

- (5 points) The set of feasible solutions to the node packing problem on a graph
G = (V,E) with n vertices and m edges can be written as
We saw in class that the convex hull of S has dimension n and the nonnegativity constraints define facets of conv(S). Give another facet of conv(S) for the given graph.

- (5 points) Find a packing of cardinality 4 in the given graph.
- (10 points) Give a set of valid inequalities that together show that there cannot be a packing of cardinality greater than 4.
- (5 points) Is the graph perfect? (Justify your answer.)
- (7 points) Find nonnegative integral node weights c
_{v}such that the optimal value of the LP relaxationis not integral.

- (8 points) The Lovasz Θ semidefinite programming relaxation of the node packing
problem has dual problem
Give a feasible solution to the dual problem with value 4.

- (5 points) The set of feasible solutions to the node packing problem on a graph
G = (V,E) with n vertices and m edges can be written as