Depth-First Branch-and-Bound Versus Local Search: A Case Study

Abstract

Depth- rst branch-and-bound (DFBnB) is a complete algorithm that is typically used to nd optimal solutions of di cult combinatorial optimization problems. It can also be adapted to an approximation algorithm and run as an anytime algorithm, which are the subjects of this paper. We compare DFBnB against the Kanellakis-Papadimitriou local search algorithm, the best known approximation algorithm, on the asymmetric Traveling Salesman Problem (ATSP), an important NP-hard problem. Our experimental results show that DF-BnB signi cantly outperforms the local search on large ATSP and various ATSP structures, nding better solutions faster than the local search; and the quality of approximate solutions from a prematurely terminated DFBnB, called truncated DFBnB, is several times better than that from the local search. 1