Past exam of the mathematics course of the University of Cambridge / 2004 / iii / Paper 33 / 5 / a

Drop the subtour elimination constraints, retaining the one-incoming/one-outgoing equations and any branch decisions. This is an assignment problem, solvable in polynomial time. Its optimum is a lower bound on the best schedule in that branch because every admissible schedule satisfies the relaxed constraints. Add the constant processing-time sum to compare completion-time bounds.

Keep a feasible schedule as an incumbent upper bound. At each branch and bound node, solve the restricted assignment problem. If it is infeasible or its bound is at least the incumbent, discard the node. If its optimum is a single tour, it is a feasible schedule attaining the bound, so update the incumbent and close the node. If it has a proper subtour $C$ with arcs $e_1,\dots ,e_r$, every valid Hamiltonian tour must omit at least one of those arcs.

For a disjoint exhaustive branching rule, child $h$ forces $e_1,\dots ,e_{h-1}$ and forbids $e_h$, for $h=1,\dots ,r$. Every valid tour falls into the child indexed by the first omitted arc. Re-solve the corresponding assignment relaxations, prioritize small bounds, and repeat. Finitely many binary choices give an exact terminating search; its worst-case tree can be exponential. Assignment optima provide lower bounds, while complete tours provide upper bounds. Patching subtours or local improvement can improve the incumbent without changing the exact pruning argument.