MATP6620/ISYE6760 Combinatorial Optimization & Integer Programming
Homework 2.

Due: Thursday, February 18, 2021, by end of day.
Penalty for late homeworks: 10% for each day or part of a day.

  1. A method for representing a spanning tree on the complete graph on vertices {1,,n} as a string of n - 2 numbers was presented in class. Find the trees with 8 vertices corresponding to the following strings:
    1. 543156.
    2. 768773.
    3. 543854.
  2. Show that
S  :=  {x ∈ B4: 97x1 +32x2 + 25x3 + 20x4 ≤ 139}
    =  {x ∈ B : 2x1 + x2 + x3 + x4 ≤ 3}
    =  {x ∈ B4 : x1 + x2 + x3 ≤ 2,x1 +x3 + x4 ≤ 2,x1 + x2 + x4 ≤ 2}.
    Which formulation do you think is most effective for solving max{cTx : x S}? Why? How do the feasible regions of the LP relaxations compare?
  3. Model the following feasibility problem as an integer programming feasibility problem:

    Given a graph G = (V,E), does there exist a partition of the edges E into two sets E1 and E2 such that neither E1 nor E2 contains a triangle?

    Is the LP relaxation to your formulation feasible?

  4. Assume you have an algorithm A for finding the minimum weight perfect matching in a graph with nonnegative edge weights. How could you use this algorithm to find the maximum weight matching in a graph G = (V,E) with nonnegative edge weights? (Note: the matching isn’t required to be perfect.)
  5. Assume we have a polynomial time algorithm for determining the optimal value of binary knapsack problems of the form max{cTx : x Bn,aTx b}. This algorithm does not tell us the values of the variables in the optimal solution. Show that we can use this algorithm as a subroutine in a polynomial time algorithm for finding the optimal solution to a binary knapsack problem.
    John Mitchell
    Amos Eaton 325
    mitchj at rpi dot edu
    Office hours: Monday and Thursday 1pm–2pm.