The Graphical Traveling Salesperson Problem has no Integer Programming Formulation in the Original Space

The Graphical Traveling Salesperson Problem (GTSP) is the problem of assigning, for a given weighted graph, a nonnegative number xe each edge e such that the induced multi-subgraph is of minimum weight among those that are spanning, connected and Eulerian. Naturally, known mixed-integer programming formulations use integer variables xe in addition to others. Denis Naddef posed the challenge of finding a (reasonably simple) mixed-integer programming formulation that has integrality constraints only on these edge variables. Recently, Carr and Simonetti (IPCO 2021) showed that such a formulation cannot consist of polynomial-time certifyiable inequality classes unless NP=coNP. In this note we establish a more rigorous result, namely that no such MIP formulation exists at all.