Consider the complete search tree Fig. 5.4 for a problem with two binary variables. The value of the relaxation is shown at each node. (a) Suppose the tree is traversed using strong branching. In what...

Consider the complete search tree Fig. 5.4 for a problem with two binary variables. The value of the relaxation is shown at each node. (a) Suppose

the tree is traversed using strong branching. In what order are the nodes processed? What is the relaxation bound θ(T) for each partial tree T constructed

during the search? (b) Now suppose the tree is traversed by maximizing θ(T)

with a steepest ascent algorithm. If adding either of two or more nodes results

in the same bound θ(T), break the tie by processing the leftmost node next.

In what order are the nodes processed? What is the bound θ(T) for each

T? Note that steepest ascent increases the bound more rapidly than strong

branching.