TY - JOUR
T1 - The Graphical Traveling Salesperson Problem has no integer programming formulation in the original space
AU - Walter, Matthias
N1 - We thank R. Carr and N. Simonetti for stimulating discussions on the challenge of Naddef as well as an anonymous referee whose comments led to an improved presentation of the material.
Publisher Copyright:
© 2021
PY - 2021/7
Y1 - 2021/7
N2 - The Graphical Traveling Salesperson Problem is the problem of assigning, for a given weighted graph, a nonnegative number xe to each edge e such that the induced multi-subgraph is of minimum weight among those that are spanning, connected and Eulerian. Known MIP formulations are based on integer variables xe. Carr and Simonetti (IPCO 2021) showed that unless NP=coNP, no (reasonable) formulation can have integrality constraints only on x-variables, a challenge posed by Denis Naddef. We establish the same result unconditionally.
AB - The Graphical Traveling Salesperson Problem is the problem of assigning, for a given weighted graph, a nonnegative number xe to each edge e such that the induced multi-subgraph is of minimum weight among those that are spanning, connected and Eulerian. Known MIP formulations are based on integer variables xe. Carr and Simonetti (IPCO 2021) showed that unless NP=coNP, no (reasonable) formulation can have integrality constraints only on x-variables, a challenge posed by Denis Naddef. We establish the same result unconditionally.
KW - Formulation
KW - Graphical Traveling Salesperson Problem
KW - Integer programming
UR - http://www.scopus.com/inward/record.url?scp=85109083298&partnerID=8YFLogxK
U2 - 10.1016/j.orl.2021.06.015
DO - 10.1016/j.orl.2021.06.015
M3 - Article
AN - SCOPUS:85109083298
VL - 49
SP - 623
EP - 624
JO - Operations research letters
JF - Operations research letters
SN - 0167-6377
IS - 4
ER -