Lower tolerance-based Branch and Bound algorithms for the ATSP

Publication year: 2012
Source: Computers & Operations Research, Volume 39, Issue 2, February 2012, Pages 291-298

Remco, Germs , Boris, Goldengorin , Marcel, Turkensteen

In this paper, we develop a new tolerance-based Branch and Bound algorithm for solving NP-hard problems. In particular, we consider the asymmetric traveling salesman problem (ATSP), an NP-hard problem with large practical relevance. The main algorithmic contribution is our lower bounding strategy that uses the expected costs of including arcs in the solution to the assignment problem relaxation of the ATSP, the so-called lower tolerance values. The computation of the lower bound requires the calculation of a large set of lower tolerances. We apply and adapt a finding from [23] that makes it possible to compute all lower tolerance values…