Consider the following optimisation problem: (a) Solve the problem by breaking it into multiple subproblems using the Branch and Bound algorithm. Implement and solve each of the subproblems into a separate sheet under the same Excel workbook. (When solving each individual subproblem in Excel, do NOT apply the integrality condition.) Save it as a single Excel file (with multiple sheets) and upload it under the textbox provided. [2 points] (b) Create a Branch and Bound Tree diagram to show the steps you have completed. Save it as a PNG file and upload it under the textbox provided. [3 points] Hints and Requirements: - You may need to apply constraints on a decision variable multiple times. (i.e. your Branch and Bound Tree diagram can have more than 4 layers). - No further branching for the current sub-problem is needed if - 1) all decision variables in the current sub-problem are integers, - 2) the solver cannot find a feasible solution for the current sub-problem, or - 3) the objective function value of the current subproblem is not as good as that of another feasible solution that has been found so far. - You may need to apply constraints on a decision variable multiple times. (i.e. your Branch and Bound Tree diagram can have more than 4 layers). - No further branching for the current sub-problem is needed if - 1) all decision variables in the current sub-problem are integers, - 2) the solver cannot find a feasible solution for the current sub-problem, or - 3) the objective function value of the current subproblem is not as good as that of another feasible solution that has been found so far. When any of these happens, add a horizontal bar under the circle of your sub-problem. For case 2), put the word "Infeasible" inside the circle of the subproblem, instead of the decision variables and the objective function value. For case 3), put "Early termination" under the bar. - Put "Optimal" under the bar of the sub-problem that can yield the best objective function value. - The first two sub-problems have been done for you. Their corresponding Excel sheets and Branch and Bound Tree diagram (half-completed) can be found below. MANU1420 2250 Assignment2 Q1 Template.xIsx RMIT Classification: Trusted \begin{tabular}{lrrrrrr} & X_1 & \multicolumn{2}{l}{ X_2 } & & & \\ Decision Variables & 1.5 & 2.545455 & & & \\ Obj Fun Coefficients & 9 & 13 & & Obj Fun & 46.59091 \\ Constraints & & & & & & \\ Const #1, Coefficients & 14 & 11 & 49 & 49 & \\ Const #2, Coefficients & 6 & 11 & 37 & 37 \end{tabular} \begin{tabular}{lrrrrrr} & X_1 & \multicolumn{2}{l}{ X_2 } & & & \\ Decision Variables & 1 & 2.818182 & & & \\ Obj Fun Coefficients & 9 & 13 & & Obj Fun & 45.63636 \\ & & & & & \\ Constraints & & & LHS & RHS & & \\ Const #1, Coefficients & 14 & 11 & 45 & 49 & \\ Const #2, Coefficients & 6 & 11 & 37 & 37 & \\ Const #3, Coefficients & 1 & 0 & 1 & 1 \end{tabular} Consider the following optimisation problem: (a) Solve the problem by breaking it into multiple subproblems using the Branch and Bound algorithm. Implement and solve each of the subproblems into a separate sheet under the same Excel workbook. (When solving each individual subproblem in Excel, do NOT apply the integrality condition.) Save it as a single Excel file (with multiple sheets) and upload it under the textbox provided. [2 points] (b) Create a Branch and Bound Tree diagram to show the steps you have completed. Save it as a PNG file and upload it under the textbox provided. [3 points] Hints and Requirements: - You may need to apply constraints on a decision variable multiple times. (i.e. your Branch and Bound Tree diagram can have more than 4 layers). - No further branching for the current sub-problem is needed if - 1) all decision variables in the current sub-problem are integers, - 2) the solver cannot find a feasible solution for the current sub-problem, or - 3) the objective function value of the current subproblem is not as good as that of another feasible solution that has been found so far. - You may need to apply constraints on a decision variable multiple times. (i.e. your Branch and Bound Tree diagram can have more than 4 layers). - No further branching for the current sub-problem is needed if - 1) all decision variables in the current sub-problem are integers, - 2) the solver cannot find a feasible solution for the current sub-problem, or - 3) the objective function value of the current subproblem is not as good as that of another feasible solution that has been found so far. When any of these happens, add a horizontal bar under the circle of your sub-problem. For case 2), put the word "Infeasible" inside the circle of the subproblem, instead of the decision variables and the objective function value. For case 3), put "Early termination" under the bar. - Put "Optimal" under the bar of the sub-problem that can yield the best objective function value. - The first two sub-problems have been done for you. Their corresponding Excel sheets and Branch and Bound Tree diagram (half-completed) can be found below. MANU1420 2250 Assignment2 Q1 Template.xIsx RMIT Classification: Trusted \begin{tabular}{lrrrrrr} & X_1 & \multicolumn{2}{l}{ X_2 } & & & \\ Decision Variables & 1.5 & 2.545455 & & & \\ Obj Fun Coefficients & 9 & 13 & & Obj Fun & 46.59091 \\ Constraints & & & & & & \\ Const #1, Coefficients & 14 & 11 & 49 & 49 & \\ Const #2, Coefficients & 6 & 11 & 37 & 37 \end{tabular} \begin{tabular}{lrrrrrr} & X_1 & \multicolumn{2}{l}{ X_2 } & & & \\ Decision Variables & 1 & 2.818182 & & & \\ Obj Fun Coefficients & 9 & 13 & & Obj Fun & 45.63636 \\ & & & & & \\ Constraints & & & LHS & RHS & & \\ Const #1, Coefficients & 14 & 11 & 45 & 49 & \\ Const #2, Coefficients & 6 & 11 & 37 & 37 & \\ Const #3, Coefficients & 1 & 0 & 1 & 1 \end{tabular}