The Graphical Traveling Salesperson Problem has no integer programming formulation in the original space

Matthias Walter*

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)623-624
Number of pages2
JournalOperations research letters
Volume49
Issue number4
DOIs
Publication statusPublished - Jul 2021

Keywords

  • Formulation
  • Graphical Traveling Salesperson Problem
  • Integer programming

Fingerprint

Dive into the research topics of 'The Graphical Traveling Salesperson Problem has no integer programming formulation in the original space'. Together they form a unique fingerprint.

Cite this