A restricted Lagrangean approach to the traveling salesman problem

摘要: We describe an algorithm for the asymmetric traveling salesman problem (TSP) using a new, restricted Lagrangean relaxation based on assignment (AP). The Lagrange multipliers are constrained so as to guarantee continued optimality of initial AP solution, thus eliminating need repeatedly solving in process computing multipliers. give several polynomially bounded procedures generating valid inequalities and taking them into function with positive multiplier without violating constraints, strengthen current lower bound. Upper bounds generated by fast tour-building heuristic. When bound-strengthening techniques exhausted matching upper bound, we branch two different rules, according situation: usual subtour breaking disjunction, new disjunction conditional bounds. discuss computational experience 120 randomly TSP's up 325 cities, maximum time used any single being 82 seconds. This is considerable improvement upon earlier methods. Though discussed here TSP, approach can be adapted symmetric TSP 2-matching instead AP.