Iterative patching and the asymmetric traveling salesman problem

Iterative patching and the asymmetric traveling salesman problem

0.00 Avg rating0 Votes
Article ID: iaor2007462
Country: Netherlands
Volume: 3
Issue: 1
Start Page Number: 63
End Page Number: 77
Publication Date: Mar 2006
Journal: Discrete Optimization
Authors: , , ,
Keywords: programming: branch and bound
Abstract:

Although Branch-and-Bound (BnB) methods are among the most widely used techniques for solving hard problems, it is still a challenge to make these methods smarter. In this paper, we investigate iterative patching, a technique in which a fixed patching procedure is applied at each node of the BnB search tree for the Asymmetric Traveling Salesman Problem. Computational experiments show that iterative patching results in general in search trees that are smaller than the usual classical BnB trees, and that solution times are lower for usual random and sparse instances. Furthermore, it turns out that, on average, iterative patching with the Contract-or-Patch procedure of Glover et al. and the Karp–Steele procedure are the fastest, and that ‘iterative’ Modified Karp–Steele patching generates the smallest search trees.

Reviews

Required fields are marked *. Your email address will not be published.