New lower bounds for the Symmetric Travelling Salesman Problem

In this paper new lower bounds for the Symmetric Travelling Salesman Problem are proposed and combined in additive bounding procedures. Efficient implementations of the algorithms are given; in particular, fast procedures for computing the linear programming reduced costs of the Shortest Spanning Tree (SST) Problem and for finding all the r-SST of a given graph, are presented. Computational results on randomly generated test problems are reported.