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 Algorithm:$**$

Depth$-$First Search $($DFS$)$ is an algorithm designed to reach the deepest nodes initially. It investi$-$

gates 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.