Relaxation & Bounds:

5. (12 points) Relaxation 8c Bounds: Consider the knapsack problem similar to the one described in our lecture notes. (P) : min 221:1 mix,- S.t-. 221:1 pails Z O x,- E {0,1} Vi: 1,2,...,n Suppose that there are 9 objects (n = 9) and that O = 50. i123456789 19,15 25 10 213191419 29 wg121251334 (a) (4 points) Apply the greedy method (by ordering the variables according to their price/weight ratio) to solve the LP relaxation of this problem (where :rg E {0,1} W = 1, 2, . . . ,n is relaxed to 0 g x, g 1 W = 1, 2, . . . , n). Does this solution provide an upper or lower bound for problem (P)? (Hint: recall that in class we used this greedy solution approach). (b) (4 points) Using the solution to the relaxation nd a feasible solution for the original problem. Compare the objective value to the lower bound. Is the resulting solution a global optimal solution? (c) (4 points) Consider solution (0, 0,0, 1, 0,0, 0,0, 1). Show that you cannot improve this solution by swapping only object 4 (the rst 1 in the solution) for any other, i.e., moving the 1 in position 4 to a di'erent position