Branch and Cut for the Symmetric Traveling Salesman Problem

by Denis Naddef, LMC-IMAG, Institut National Polytechnique de Grenoble and EPFL

We will first briefly describe the branch and cut algorithm and point out
the efforts that have to be made in order to have it perform correctly. In
particular we will see that there is an important mathematical effort which
consists in the study of the description of a certain polytope, known as
the  Traveling Salesman Polytope, by linear inequalities. We will give an
overview of the Traveling Salesman Polytope and explain intuitively the
meaning of some important classes of linear inequalities. We then show the
role of such inequalities in the solution procedure. Extensive
computational results will be given on instances taken from the TSPLIB.