Consider the following IP problem. maximize :

7x1 +28x2 12x3 +15x4 +5x5

subject to :

50x1 70x2 +40x3 +30x4 30x5 100 10x1 +60x2 +50x3 +60x4 20x5 80

6x1+ 1x2+ 3x3+ 7x49 xi {0,1} i = 1,...,5

(a) Write the LP relaxation of the above model.

(b) Get the optimal objective function value of the LP relaxation from Table 1. Is it a lower or an upper bound? Explain.

(c) Is x = [1, 0, 0, 0, 1]T a feasible solution to the above problem. If yes, then obtain its objective function value from Table 1. Is it a lower or an upper bound? Explain.

Solve the above problem using branch & bound method, and build the enumeration tree using the following strategies. You can use the information from Table 1.