Problem 3: (The Branch and Bound Method) [20 points] During the maximization of a pure IP problem by the branch and bound algorithm, we have constructed the following branch and bound tree at a certain stage. Z = 75 (Integer Solution) Node 4 LP-4 Z=85 (Continuous Solution) Node 2 LP-2 251 222 Z = 95 (Continuous Solution) 4151 Infeasible Solution Node 5 LP-5 Node 1 LP-1 x22 Z=80 (Continuous Solution) Z = 77 (Continuous Solution) Node 6 LP-6 Node 3 LP-3 X252 X223 Z = 73 (Continuous Solution) Node 7 LP-7 (a) (4 points) What is the best value of Z for an integer solution known until now? (b) (4 points) What is the best value of Z we might get? (c) (4 points) Indicate the node(s) that have been fathomed (killed) and which are branched, explain why. (d) (4 points) Is the optimal solution to the integer program reached? Why or why not? (e) (4 points) Describe the work of the Cut-and-Branch and Branch-and-Cut algorithms Problem 3: (The Branch and Bound Method) [20 points] During the maximization of a pure IP problem by the branch and bound algorithm, we have constructed the following branch and bound tree at a certain stage. Z = 75 (Integer Solution) Node 4 LP-4 Z=85 (Continuous Solution) Node 2 LP-2 251 222 Z = 95 (Continuous Solution) 4151 Infeasible Solution Node 5 LP-5 Node 1 LP-1 x22 Z=80 (Continuous Solution) Z = 77 (Continuous Solution) Node 6 LP-6 Node 3 LP-3 X252 X223 Z = 73 (Continuous Solution) Node 7 LP-7 (a) (4 points) What is the best value of Z for an integer solution known until now? (b) (4 points) What is the best value of Z we might get? (c) (4 points) Indicate the node(s) that have been fathomed (killed) and which are branched, explain why. (d) (4 points) Is the optimal solution to the integer program reached? Why or why not? (e) (4 points) Describe the work of the Cut-and-Branch and Branch-and-Cut algorithms