MATP6620/ISYE6760 Combinatorial Optimization & Integer Programming
Homework 2.
Solutions

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.

    Solution:

  2. Show that
                 4
S  :=  {x ∈ B : 97x1 +32x2 + 25x3 + 20x4 ≤ 139}
    =  {x ∈ B4 : 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?

    Solution:

    The three formulations of S are equivalent since all three sets consist of the points

    (1,1,0,0),(1,0,1,0),(1,0,0,1),(0,1,1,1)

    and all binary points that are smaller than at least one of these points.

    The most effective formulation is the one with the tightest LP relaxation. Denote the feasible regions of the LP relaxations as

    S1 :=  {x ∈ ℝ4 : 97x1 + 32x2 + 25x3 + 20x4 ≤ 139,0 ≤ x ≤ e}
S2 :=  {x ∈ ℝ4 : 2x1 + x2 + x3 + x4 ≤ 3,0 ≤ x ≤ e}
             4
S3 :=  {x ∈ ℝ  : x1 + x2 + x3 ≤ 2,x1 + x3 + x4 ≤ 2,x1 +x2 + x4 ≤ 2,0 ≤ x ≤ e}
    where e denotes the vector of ones. Note that
    x = (0.5,1,1,0) ∈ S2 \ S3

    while

    x = (0.5,0.75,0.75,0.75) ∈ S \S ,
                       3   2

    so neither set contains the other.

    If x S2 then

    32(2x1 + x2 + x3 + x4)+ 33x1 ≤ 32(3)+ 33,

    or equivalently

    97x1 + 32x2 + 32x3 +32x4 ≤ 129,

    which dominates the inequality defining S1, so S2 S1.

    Similarly, if x S3 then

    18.5(x1 + x2 + x3)+ 6.5(x1 + x3 + x4)+ 13.5(x1 + x2 + x4) + 58.5x1 ≤ 18.5(2) + 6.5(2)+ 13.5(2)+ 58.5,

    or equivalently

    97x1 +32x2 + 25x3 + 20x4 ≤ 135.5,

    which dominates the inequality defining S1, so S2 S1.

    Thus, S1 is the weakest formulation. It is not easy to compare the other two formulations; the better one will depend on the objective function. The inequalities in the third formulation can be obtained by one C-G rounding from the second formulation, and vice versa.

  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?

    Solution:

    Let the binary variable indicate whether an edge is in E1, so we want

         {
xe =   1  if e ∈ E1
       0  if e ∈ E2

    If three edges constitute a triangle in E then we need the sum of their x-values to be either 1 or 2. Otherwise, if the sum is 3 then all three edges are in E1, and if the sum is 0 then all three edges are in E2. So the binary variables xe must satisfy the constraints

    1 ≤ xe + xf + xg ≤ 2 for all triangles e,f,g ∈ E.

    The LP relaxation is feasible: take all xe = 0.5.

    Note that the original combinatorial feasibility problem is not necessarily feasible: consider the case of a complete graph on 6 vertices.

  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.)

    Solution:

    If |V | is odd, we first add an extra vertex.

    We then complete the graph, giving the added edges length 0 so any maximum weight matching is still a maximum weight matching.

    Let W be the largest edge weight.

    We create a perfect matching problem by using new weights

    we = W  - we.

    Note that any perfect matching uses exactly ⌈|V |2edges. Let M be a matching in the original graph. With the construction, this corresponds to a matching M in the modified graph. Because every perfect matching contains the same number of edges, we have

     ∑                  ∑
    we = ⌈|V |∕2⌉W -     we,
e∈M                e∈M

    so finding the minimum weight perfect matching is equivalent to finding the maximum weight matching in the original graph.

  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.

    Solution:

    We can find the optimal value of n + 1 binary knapsack problems. At each iteration, the number of variables in the knapsack problem is reduced, and the right hand side might be changed. We define

            {  k              k       }
vk=  max  ∑  cx  : x ∈ Bk, ∑ ax ≤ q .
 q        i=1 i i        i=1  ii

    Algorithm:

    1. Initialize with k = n, q = b, and find the value vbn of the original problem. Initialize the set of objects in the optimal solution to S = .
    2. Reoptimize to find vqk-1.
      • If vqk-1 = vqk then object k is unnecessary, so can set xk = 0 permanently.
      • If vqk-1 < vqk then object k is necessary, so can set S = S ∪{k}. Update q q - ak.
    3. Set k = k - 1.
    4. If k 1, return to 5b.

      Otherwise, STOP and return S.

    Note that the algorithm works even if there are multiple optimal solutions: an item is discarded if and only if there is an optimal solution remaining that doesn’t include the item. The particular solution returned depends on the ordering of the items.

    John Mitchell
    Amos Eaton 325
    x6915.
    mitchj at rpi dot edu
    Office hours: Monday and Thursday 1pm–2pm.
    webex: https://rensselaer.webex.com/meet/mitchj