An improved branching rule for the symmetric travelling salesman problem

Abstract

This paper presents an improvement to an existing branch and bound algorithm for solving the symmetric travelling salesman problem. The lower bound used is the standard one obtained from the sequence of minimal spanning 1-trees computed via subgradient optimization, but the branching rule is new. Rather than selecting for inclusion or exclusion those edges which violate the tour constraints in the final 1-tree of the sequence, we consider edges which are present in roughly half of the final few 1-trees. This results in a decision tree whose number of nodes grows by powers of two rather than three, hence significantly reducing the total number of decision nodes required to solve the problem.

Keywords:

• travelling salesman
• branch-and-bound
• 1-tree relaxation