5- (25 pts)Consider the integer linear program (ILP) below. maximize 3x1 + 2x2 subject to 4x1 + 2x2 0 and integer All linear programming subproblem solutions of the branch&bound tree are reported in the following table(randomly ordered): Objective value 12.5 12 Subproblem LP1 LP1 + (x123) LP1 + (x1 2 3,x2 2 2) LP1 + (x1 2 3,X2 4) LP relaxation solution (X1, X2) (2.5,2.5) (3,1.5) Infeasible (3.5,1) (2,3) (3,1) Infeasible 11.75 12 11 a) Draw the branch&bound tree based on the solutions above using the rules: start branching on variable x1, use depth-first search (go deeper in tree as possible with branching), prefer > first while branching on a variable. Name the subproblems on the tree such as LP1, LP2,... Show the constraint added on each branch such as x > 3. b) What are the best upper bound and lower bound values