= 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.
Back to article page
