A New Integer Programming Formulation of the Graphical Traveling Salesman Problem

Robert D. Carr, Neil Simonetti

In the Traveling Salesman Problem (TSP), a salesman wants to visit a set of cities and return home. There is a cost $c_{ij}$ of traveling from city $i$ to city $j$, which is the sa…