• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Of all publications in the section: 1
Sort:
by name
by year
Book chapter
Alexey Nikolaev, Mikhail Batsyn. In bk.: Combinatorial Algorithms. 29th International Workshop, IWOCA 2018, Singapore, July 16–19, 2018. Lecture Notes in Computer Science. Vol. 10979. Springer, 2018. P. 311-322.

In this paper a branch-and-bound algorithm for the Symmetric Travelling Salesman Problem (STSP) is presented. The algorithm is based on the 1-tree Lagrangian relaxation. A new branching strategy is suggested in which the algorithm branches on the 1-tree edge belonging to the vertex with maximum degree in the 1-tree and having the maximum tolerance. This strategy is compared with} branching on the shortest edge and the so-called strong branching, which is the branching on the edge with maximum tolerance also applied by Held & Karp (1971). The computational experiments show that {proposed} branching strategy provides better results on TSPlib benchmark instances.

Added: Oct 23, 2018