A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems

TLDR

The benchmark set includes medium‑size problems from the literature and large‑scale real‑world instances. The study presents an algorithm that solves large‑scale symmetric TSP instances to optimality. The algorithm combines a polyhedral cutting‑plane procedure that generates cuts from a subset of the convex‑hull inequalities with a tree‑search strategy that continues to add cuts after branching, implemented in FORTRAN and interfaced with two LP solvers. Experiments on 42 STSPs ranging from 48 to 2,392 nodes show that all instances are solved to optimality within reasonable computation times.

Abstract

An algorithm is described for solving large-scale instances of the Symmetric Traveling Salesman Problem (STSP) to optimality. The core of the algorithm is a "polyhedral" cutting-plane procedure that exploits a subset of the system of linear inequalities defining the convex hull of the incidence vectors of the hamiltonian cycles of a complete graph. The cuts are generated by several identification procedures that have been described in a companion paper. Whenever the cutting-plane procedure does not terminate with an optimal solution the algorithm uses a tree-search strategy that, as opposed to branch-and-bound, keeps on producing cuts after branching. The algorithm has been implemented in FORTRAN. Two different linear programming (LP) packages have been used as the LP solver. The implementation of the algorithm and the interface with one of the LP solvers is described in sufficient detail to permit the replication of our experiments. Computational results are reported with up to 42 STSPs with sizes ranging from 48 to 2,392 nodes. Most of the medium-sized test problems are taken from the literature; all others are large-scale real-world problems. All of the instances considered in this study were solved to optimality by the algorithm in "reasonable" computation times.