MATP6620 / ISYE6760 Integer and Combinatorial Optimization
Homework 4.
Solutions

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

    When x2 = 1, we have the valid constraint

    x1 + x3 + x4 ≤ 2.
    (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.)

    Solution:

    With the given change of variables, (1) is equivalent to the constraint

    7x1 - 4(1- z2)+ 6x3 + 4x4 ≤ 9

    or equivalently

    7x1 + 4z2 + 6x3 + 4x4 ≤ 13.
    (3)

    This is now in our framework for lifting: we have a valid constraint (2) in x1, x3, x4 when z2 = 0. To find the lifting coefficient, we solve:

    ζ :=  max{x1 + x3 + x4 : 7x1 +4z2 +6x3 + 4x4 ≤ 13,z2 = 1,x1,z2,x3,x4 binary} = 1,

    achieved by multiple solutions including x1 = 0, x3 = 1, x4 = 0, z2 = 0. Hence the lifting coefficient is 2 - ζ = 1, so the lifted constraint is

    x1 + z2 + x3 + x4 ≤ 2.

    Expressing this in terms of the original variables, we have the valid constraint

    x1 + (1 - x2)+ x3 + x4 ≤ 2,

    or equivalently

    x1 - x2 +x3 + x4 ≤ 1.

  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
                    T
max            cTx
subject to ∑   a x  ≤   b
             j∈Ni xj ≤   1n  for i = 1,...,k
                 x  ∈   B

    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.

    Solution:

    1. Feasible solutions to the knapsack problem include the empty set and the n sets consisting of just one item. Hence the convex hull of S is full-dimensional.
    2. There are |Ni| packings that satisfy the constraint at equality, namely the packings consisting of exactly one item from Ni. Let
      Żai := min{aj : j ∈ Ni}, and ki ∈ argmin{aj : j ∈ Ni },

      so ak = ai, k Ni.

      Assume aj b -ai for every j ⁄∈ Ni. Then each j ⁄∈ Ni is in the valid solution {j,k}.

      The incidence vectors of the given n packings are linearly independent, so they are affinely independent, so the given constraint defines a facet provided the assumption holds.

  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
j∈C
    (4)

    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)

    Solution:

    Because of the constraint that at most one item can be picked from each subset, we must have

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

    with equality only if exactly one item j with aj aj(i) is chosen from each set Ni.

    If exactly one such item is picked from each set Ni with |C Ni| = 1 then

           (               )
  ∑          ∑                ∑           ∑
       (           ajxj) ≥         aj(i) =    aj > b,
i:C∩Ni⁄=∅  j∈Ni:aj≥aj(i)         i:C∩Ni⁄=∅      j∈C

    since C is a cover. Hence it is not possible to pick exactly one item from each set Ni with the item j from set Ni satisfying aj aj(i), so the constraint in the question is valid.

  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   20x1  +  30x2  +  40x3  +  42x4
s.t.    x1  +   3x2  +   5x3  +   6x4  ≤  7
                                   xi  binary

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

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

    Solution:

    1. Solution to LP relaxation is x = (1,1,0.6,0). This leads to the minimal cover {2,3} and the minimal cover inequality
      x2 + x3 ≤ 1.

      Lifting on x1 and then x4 gives the facet defining inequality

      x2 +x3 + x4 ≤ 1.

      Lifting in the other order gives the same inequality.

    2. Solution to LP relaxation is x = (0,13,0,1). This leads to the minimal cover {2,4} and the minimal cover inequality
      x2 + x4 ≤ 1.

      Lifting on x1 and then x3 gives the facet defining inequality

      x2 +x3 + x4 ≤ 1.

      Lifting in the other order gives the same inequality.

    3. Solution to LP relaxation is x = (1,0.4,1,0). This leads to the minimal cover {1,2,3} and the minimal cover inequality
      x2 + x3 ≤ 1.

      Lifting on x1 and then x4 gives the facet defining inequality

      x2 +x3 + x4 ≤ 1.

      Lifting in the other order gives the same inequality.

  5. The linearly dependent vectors x1,,xm in n are all on the hyperplane aTx = b, where b0. Show that they are affinely dependent.

    Solution:

    There exist multipliers λ1,m, not all zero, with

    ∑m    i
   λix = 0.
i=1

    It follows that

           m         m            m
0 = aT(∑  λixi) = ∑  λiaTxi = b∑ λi.
       i=1        i=1          i=1

    Hence, i=1mλi = 0 so the vectors are affinely dependent.

    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