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: | Sierksma Gerard, Ghosh Diptesh, Goldengorin Boris, Turkensteen Marcel |
Keywords: | programming: branch and bound |
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