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

2021/06/18 by Walter, Matthias
#90C11 #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.1.6 #G.2.2 #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2106.10097

Abstract

The Graphical Traveling Salesperson Problem (GTSP) is the problem of assigning, for a given weighted graph, a nonnegative number x_e 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 x_e 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.

Related

• A New Integer Programming Formulation of the Graphical Traveling Salesman Problem
• Improved integrality gap upper bounds for TSP with distances one and two
• Approximate solutions to the Travelling Salesperson Problem on semimetric graphs
• Extension Complexity Lower Bounds for Mixed-Integer Extended Formulations
• On Polynomial Kernels for Traveling Salesperson Problem and its Generalizations