Name: |

MATP6620/ISYE6770

Integer and Combinatorial Optimization

Spring 2019

Midterm Exam, Friday, March 29, 2019.

Solutions

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 | /20 | |

Q5 | /20 | |

Total | /100 |

- (20 points) For each of the following feasibility problems, indicate if it is polynomially
solvable or -complete. (No partial credit. 4 points per part, -1 point for incorrect
answers.)
- Node packing with lower bound: Given a graph G = (V,E) and an integer k, does
there exist a node packing of cardinality at least k?
Polynomially solvable -complete

- Perfect matching: Given a graph G = (V,E), does there exist a perfect matching?
Polynomially solvable -complete

- Minimum spanning tree with upper bound Given a graph G = (V,E), edge weights w
_{e}for e ∈ E, and an integer W, does there exist a spanning tree with total weight no larger than W?Polynomially solvable -complete

- Traveling salesman problem with upper bound: Given a complete graph on vertices V ,
with integer edge weights w
_{e}, and a positive integer W, does there exist a traveling salesman tour of length no more than W?Polynomially solvable -complete

- Binary knapsack problem with lower bound: Given a ∈ ℤ
^{n}, c ∈ ℤ^{n}, and scalars b and z, does there exist a binary x ∈ ℤ^{n}with a^{T }x ≤ b and c^{T }x ≥ z?Polynomially solvable -complete

- Node packing with lower bound: Given a graph G = (V,E) and an integer k, does
there exist a node packing of cardinality at least k?
- The binary variables x
_{1},…,x_{5}satisfy the constraints- (4 points) Show the constraints
have Chvatal rank equal to one.

- (8 points) Show the valid constraint
has Chvatal rank no greater than 3.

- (8 points) Show the valid constraint
has Chvatal rank at least 2.

Solution:

- We take 0.5 of the original constraint and round down:
- We use the rank 1 inequality from part (a) to construct the rank 2 inequalities with
sums of 4 variables, and then combine these to give the desired inequality, so it has rank
no greater than 3:
For any 1 ≤ i < j < k < l ≤ 5, we take of the four inequaities from part (a) involving these variables:

We now take of these 5 inequalities to give

as required.

- The optimal solution to the LP relaxation with objective function max ∑
_{j=1}^{5}x_{ j}is x = (,,,,), with value 4. Since this value is greater than 3, the desired inequality cannot have Chvatal rank 1.

- (4 points) Show the constraints
- Consider the problem
- (10 points) Give the next level of the branch-and-bound tree using standard
branch-and-bound. You need only give the optimal value at each node, together with
the fathoming decision. Note that in an optimal solution to a relaxation, all the
variables that take non binary values take the same value.
- (10 points) Give the tree you obtain if you use orbital branching. How many LP
subproblems do you solve?
Thus, we need only solve 7 linear programs.

- (10 points) Give the next level of the branch-and-bound tree using standard
branch-and-bound. You need only give the optimal value at each node, together with
the fathoming decision. Note that in an optimal solution to a relaxation, all the
variables that take non binary values take the same value.
- (20 points)
- (8 points) The nonnegative integer variable y
_{1}and the nonnegative continuous variable x must satisfyGive a valid linear constraint that is violated by the point x = 0, y = 4.

- (12 points) Let y
_{2}be a binary variable. Assume in addition that y_{1}and y_{2}must satisfyLift the constraint you found in part 4a to give a valid constraint in x, y

_{1}, and y_{2}.

Solution:

- The mixed integer cut is
where f = , the fractional part of the right hand side. Can rewrite this as

- The lifting subproblem is
Optimal solution is x = 3, y

_{1}= 1, y_{2}= 1, with value 11. Taking the difference between this value and the right hand side of 5 for the constraint shows that y_{2}has coefficient -6, so the lifted constraint is

- (8 points) The nonnegative integer variable y
- The wheel W
_{n}is a graph G = (V,E) with n + 1 vertices labelled 0, 1,…,n. It has 2n edges, of the form (1, 2), (2, 3), …, (n - 1,n), (1,n), and (0,i) for i = 1,…,n. Our feasible region S consists of all incidence vectors of Hamiltonian cycles on W_{n}.Every feasible solution satisfies the n + 1 degree constraints

You may assume these equality constraints are linearly independent. (Hint: Let M be a square matrix with every entry equal to one. Let I be the identity matrix. You may assume that the columns of the matrix M - I are linearly independent.)

- (4 points) How many feasible solutions are there?
- (8 points) Show that the dimension of the feasible region is n - 1.
- (8 points) Show that the constraints x
_{e}≤ 1 define facets of conv(S) for the edges (1, 2), (2, 3), …, (n - 1,n), (1,n).

Solution:

- There are n feasible solutions: omit one of the rim edges.
- If we order the n rim edges first, the first n components of the incidence vectors
of our n solutions give the columns of the matrix M - I. Thus, these incidence
vectors are linearly independent, so they are affinely independent. Therefore, the
dimension of the feasible region is at least n - 1.
The region S satisfies n + 1 linearly independent equality constraint, so the dimension of the feasible region is no greater than 2n - (n + 1) = n - 1.

- Just one of the feasible solutions does not satisfy x
_{e}= 1 for the listed edges. Hence, we have n-1 feasible solutions that satisfy the constraint at equality. From part (b), these feasible solutions are linearly independent, so they are affinely independent. Thus, the dimension of the face is at least n - 2, so it is a facet.