Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 38 / 6

A branch and bound algorithm partitions the feasible set into subproblems and attaches a valid lower bound to each subproblem's possible objective value. A completed feasible solution supplies an incumbent upper bound. For minimization, discard a node if it is infeasible or its lower bound is at least the incumbent; otherwise branch by fixing an additional decision. The best-bound search rule expands the active node with the smallest lower bound. Once every active bound is at least the incumbent, the incumbent is optimal.

For this assignment problem, use the assignment lower bound from independent task minima. For a partial assignment $P$, with unassigned machines $M$ and unassigned tasks $J$, it isThis may reuse the same machine in several minima. Relaxing the distinct-machine constraint only reduces the cost, so the resulting lower bound is valid.

The given tree has already expanded the $a=2$ node of bound $58$, then its $b=3$ child of bound $59$. That child completes to $(a,b,c,d)=(2,3,1,4)$ at cost $12+13+11+28=64$, or $(2,3,4,1)$ at cost $12+13+23+17=65$. Thus we have an incumbent $64$. The best remaining active node is $a=1$, with lower bound $60$. Its three branches have boundsThe first and third children cannot improve the incumbent. Expand $a=1,b=3$, the sole active bound below $64$. Its last two possible completions areUpdate the incumbent to $61$. The unexpanded nodes have bounds $64,65,66,68,68,78$, all at least $61$; the other completed leaves are also more expensive. The branch and bound search therefore terminates, withThe additional expansion order after the supplied tree is $a=1$, then $a=1,b=3$. The feasible assignment of cost $61$ and the bounds excluding every remaining branch together certify global optimality.