Consider the following IP problem. maximize:7x1+28x212x3+15x4+5x5subjectto:50x170x2+40x3+30x430x510010x1+60x2+50x3+60x420x5806x1+1x2+3x3+7x49xi{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. Note: Generate one tree for Part (d), one for Part (e) and one for Part (f). Draw inside each node, the node number. Next to each node write objective function value and all the fractional variables. Draw the branch down (or bounds) on the left side, and the branch up (or ) bounds on the right side. While generating the tree, you should follow the strategies as described. During the execution of any strategy, if the number of nodes processed is greater than or equal to 20, then you can terminate the strategy. Report the incumbent solution. Also, say in percentage, how far it is from the best possible solution. For Strategy-1, write the LP formulation that was solved at every 5th node. (d) Strategy-1: - Node Selection: Best First Select the node with the best objective function value. - Variable Selection: Nearest to integer A fractional variable with fractional value nearest to an integer will be used for branching. - Branching Direction: Up Select the branch of side (lower bound is increased.) (e) Strategy-2: - Node Selection: Depth First the Best Back Select the most recently created child node to solve. If no child exists, then backtrack to the best bound node available in the entire tree. - Variable Selection: Lowest fraction A fractional variable with lowest fraction will be used for branching. - Branching Direction: Down Select the branch of side (upper bound is decreased.) (f) Strategy-3: - Node Selection: Breadth First the Best Next All nodes at one level of the search tree are processed before any node at a deeper level. In a given level, best node should be processed first. - Variable Selection: Highest fraction A fractional variable with highest fraction will be used for branching. - Branching Direction: You are free to pick any rule