 Assignment relaxation of the travelling salesman problem

Minimizing ${\sum }_{ij}{c}_{ij}{x}_{ij}$ over binary variables with one outgoing and one incoming edge at every graph vertex, and $x_{ii}=0$, is an assignment problem. Its feasible solutions are cycle covers of a directed graph, whereas a travelling salesman problem requires one Hamiltonian cycle. The relaxed minimum is therefore a lower bound on the tour cost. If its optimum contains a proper subtour $C$, every tour omits at least one edge of $C$. Branching into subproblems that respectively forbid each edge of $C$ preserves every possible tour. Solving each child assignment problem and pruning those whose bounds exceed the best tour yields a finite branch and bound algorithm. Equality also permits pruning when only one optimum is wanted.