= Solution
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,\ldots,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,\ldots,e_{h-1}$ and forbids $e_h$, for $h=1,\ldots,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. \b[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.
Back to article page
