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

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 17

Search

Depth-first branch-and-bound (DFBnB) is a complete algorithm that is typically used to find optimal solutions of difficult combinatorial optimization problems. It can also be adapted to an approximation algorithm and run as an anytime algorithm. In this paper, we study DFBnB as an approximation and anytime algorithm. 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 DFBnB significantly outperforms the local search on large ATSP and various ATSP structures, finding 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.