1. (30 pts.) Consider the following IP problem. Maximize 2 = 11x + 4x2 s.t. 5x, + 2x516 2x7 - X2 54 --X, + 2xy S4 *:.X220 integer a) (6 pts.) Solve the IP model graphically. b) (6 pts.) Solve the IP's LP relaxation graphically. State the optimal solution and the value of Z? c) (6 pts.) For your answer in (b) round the solution to the nearest integer value and check for feasibility. State possible rounding strategy (i.c., rounding up or down) for each variable and check feasibility and optimality in each case. Are any of these feasible rounded solutions optimal for the IP problem? Explain. d) (12 pts.) Solve the IP model using the Branch-and-Bound method by starting the branching on x. Draw the Branch and Bound tree (refer to page 532 in the book for the proper formatting), You may stop either when you find the optimal solution or when you complete 15 sub- problems. Each node should contain information showing the current lower bound. upper bound, incumbent and fathomed nodes after each iteration according to this diagram: X-1 Node/SP 2 LP Relaxation (SP) + X - (X, X, X, X.) - (1,0.714, 1, 0), 2= 21.85 UB. 21.85 Incumbent = 19 (1, 1, 0, 0)