  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 same in either direction for the Symmetric TSP. The
objective is to visit each city exactly once, minimizing total travel costs. In
the Graphical TSP, a city may be visited more than once, which may be necessary
on a sparse graph. We present a new integer programming formulation for the
Graphical TSP requiring only two classes of constraints that are either
polynomial in number or polynomially separable, while addressing an open
question proposed by Denis Naddef.
