New lower bounds for the Symmetric Travelling Salesman Problem |
| |
| Authors: | G. Carpaneto M. Fischetti P. Toth |
| |
| Affiliation: | (1) Dipartimento di Economia Politica, University of Modena, Italy;(2) DEIS, University of Bologna, Italy |
| |
| Abstract: | 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 ther-SST of a given graph, are presented. Computational results on randomly generated test problems are reported. |
| |
| Keywords: | Symmetric Travelling Salesman Problem additive bounding procedures reduced costs computation algorithms implementation |
| 本文献已被 SpringerLink 等数据库收录！ |
