MATP6620 / ISYE6760 Integer and Combinatorial Optimization
Homework 4.

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

  1. Let S be the set of binary variables x B4 satisfying
    7x1 - 4x2 +6x3 + 4x4 ≤ 9.

    When x2 = 1, we have the valid constraint

    x1 + x3 + x4 ≤ 2.

    Lift the inequality to give a valid inequality for S. (Hint: consider a change of variables z2 := 1 - x2. Make sure you convert your constraint back to the x variables.)

  2. The multiple choice knapsack problem is a knapsack problem with the additional restriction that at most one item can be picked from k disjoint subsets Ni of the items N = {1,,n}. This can be written
    max            cTx
subject to ∑   aTx  ≤   b
             j∈Ni xj ≤   1   for i = 1,...,k
                 x  ∈   Bn

    where a,c +n. Assume aj b for j = 1,,n. Let S denote the set of feasible solutions.

    1. Prove that the convex hull of S has dimension n.
    2. Give a condition on the entries of a that guarantees that the inequality jNixj 1 defines a facet of the convex hull of S. Prove it is a facet when your condition is satisfied.
  3. Let C be a minimal cover for the multiple choice knapsack problem of Question 2, with |C Ni|≤ 1 for i = 1,,k. The inequality
   xj ≤ |C|- 1

    is a valid inequality. Let {j(i)} = C Ni when C Ni. Prove the following inequality is also valid:

           (             )
  ∑         ∑
       (           xj) ≤ |C|- 1
i:C∩Ni⁄=∅  j∈Ni:aj≥aj(i)

  4. For each of the following binary knapsack problems, solve the linear programming relaxation, give a valid cover inequality violated by the solution to the relaxation, and lift the inequality to give a facet defining inequality.
    1. max   20x   +  30x   +  40x   +  42x
s.t.    x1  +   3x2  +   5x3  +   6x4  ≤  7
         1        2        3       x4  binary

    2. max  4x1  +   15x2 +   22x3 +   42x4
s.t.   x1  +    3x2 +    5x3 +    6x4  ≤  7
                                  xi  binary

    3. max   13x1  +  25x2  +  18x3  +  27x4
s.t.   2x1  +   5x2  +   3x3  +   6x4  ≤  7
                                   xi  binary

  5. The linearly dependent vectors x1,,xm in n are all on the hyperplane aTx = b, where b0. Show that they are affinely dependent.
    John Mitchell
    Amos Eaton 325
    mitchj at rpi dot edu
    Office hours: Monday and Thursday 1pm–2pm.