Truncated and Anytime Depth-First Branch and Bound: A Case Study on the Asymmetric Traveling Salesman Problem

Search Techniques for Problem Solving Under Uncertainty and Incomplete Information

Volume

Search Techniques for Problem Solving Under Uncertainty and Incomplete Information

Contents

One of the most applied search algorithms for finding optimal solutions in practice is depthfirst branch and bound (DFBnB), and the most popular method for approximate solutions is local search. Besides the fact that DFBnB is typically applied to obtain optimal solutions, it can also be used to find approximate solutions, and can also run as an anytime algorithm. In this paper, we study DFBnB used as approximation and anytime algorithms. We compare DFBnB against a local search algorithm, which is the best approximation algorithm we found, on the asymmetric Traveling Salesman Problem (ATSP), an important NPcomplete problem. Our experimental results on the ATSP, up to 1,000 cities, show that DFBnB significantly outperforms the local search algorithm on various ATSP structures, finding better solutions much earlier than the local search; and the quality of approximate ATSP tours from a truncated DFBnB is typically several times better than that from the local search. Our study demonstrates that DFBnB is highperformance anytime and approximation algorithms for solving large problems.