Question $4$

$(20$ points$)$ Presented here is a decision tree for the branch and bound algorithm applied to a maximization problem. Each node shows the objective value of the LP relaxation and specifies if it includes an integer solution.

Depth$-$First Search $($DFS$)$ is an algorithm designed to reach the deepest nodes initially. It investigates each node through recursion and traverses to the end of each branch prior to backtracking. DFS is advantageous for examining all potential solutions in a branch and bound algorithm.

$(5$ points$)$ What do the upper bound and lower bound represent for this problem?

$(15$ points$)$ Using the Depth$-$First Search algorithm, find the optimal solution in the decision tree above. Update the upper and lower bounds at each step and clearly indicate if the solution is at an integer node.