Tolerance-based branch and bound algorithms for the ATSP
View/ Open
Date
2008-11-09Author
Turkensteen, M.
Ghosh, Diptesh
Goldengorin, B.
Sierksma, G.
Metadata
Show full item recordAbstract
The selection of entries to be included/excluded in Branch and Bound algorithms is usually done on the basis of cost
values. We consider the class of Depth First Search algorithms, and we propose to use upper tolerances to guide the search
for optimal solutions. In spite of the fact that it needs time to calculate tolerances, our computational experiments for
Asymmetric Traveling Salesman Problems show that in most situations tolerance-based algorithms outperform cost-based
algorithms. The solution time reductions are mainly caused by the fact that the branching process becomes much more
effective, so that optimal solutions are found in an earlier stage of the branching process. The use of tolerances also reveals
why the widely used choice for branching on a smallest cycle in assignment solutions is on average the most effective one.
Moreover, it turns out that tolerance-based DFS algorithms are better in solving difficult instances than the Best First
Search algorithm from Carpaneto et al.
Collections
- Journal Articles [3729]