Problem 3. Cutting planes for knapsack problem. You are given the following knapsack problem: item 1 23 4 5 size 31 28 45 18 25 benefit 43 35 50 24 30 The knapsack size is 60. Multiple copies of the same item can be taken. a) Give an integer programming formulation for this problem. b) Recall that for k=1 and S={i wi>W/k), we have the following cutting plane: x, sk-1 LES Add cutting planes for k=2, 3, 4 to the formulation of part (a). Problem 3. Cutting planes for knapsack problem. You are given the following knapsack problem: item 1 23 4 5 size 31 28 45 18 25 benefit 43 35 50 24 30 The knapsack size is 60. Multiple copies of the same item can be taken. a) Give an integer programming formulation for this problem. b) Recall that for k=1 and S={i wi>W/k), we have the following cutting plane: x, sk-1 LES Add cutting planes for k=2, 3, 4 to the formulation of part (a)