The Solution of some 100-city Travelling Salesman Problems

Abstract

A simplex-based FORTRAN code, working entirely in integer arithmetic, has been developed for the exact solution of travelling-salesman problems. The code adds tour-barring constraints as they are found to be violated. It deals with fractional solutions by adding two-matching constraints and as a last resort by ‘Gomory’ cutting plane constraints of the Method of Integer Forms. Most of the calculations are carried out on only a subset of the variables, with only occasional passes through the whole set of possible variables. Computational experience on some 100-city problems is reported.

Keywords

• Travelling salesman problem
• Cut-and-price
• Combinatorial optimization