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

When x2 = 1, we have the valid constraint (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 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 (3)

is a valid inequality. Let {j(i)} = C Ni when C Ni. Prove the following inequality is also 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. 2. 3. 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 x6915. mitchj at rpi dot edu Office hours: Monday and Thursday 1pm–2pm. webex: https://rensselaer.webex.com/meet/mitchj