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

Matthias Walter

doi:10.1016/j.orl.2021.06.015

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

Matthias Walter^*

^*Corresponding author for this work

Mathematics of Operations Research

Research output: Contribution to journal › Article › Academic › peer-review

90 Downloads (Pure)

Abstract

The Graphical Traveling Salesperson Problem is the problem of assigning, for a given weighted graph, a nonnegative number x_e 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 x_e. 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 language	English
Pages (from-to)	623-624
Number of pages	2
Journal	Operations research letters
Volume	49
Issue number	4
DOIs	https://doi.org/10.1016/j.orl.2021.06.015
Publication status	Published - Jul 2021

Keywords

UT-Hybrid-D
Graphical Traveling Salesperson Problem
Integer programming
Formulation

Access to Document

10.1016/j.orl.2021.06.015Licence: CC BY

Walter-2021-The-graphical-traveling-salespersonFinal published version, 171 KBLicence: CC BY

Cite this

@article{4d8ae42b3a4d4d75b941564252e68d66,

title = "The Graphical Traveling Salesperson Problem has no integer programming formulation in the original space",

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.",

keywords = "UT-Hybrid-D, Graphical Traveling Salesperson Problem, Integer programming, Formulation",

author = "Matthias Walter",

note = "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: {\textcopyright} 2021",

year = "2021",

month = jul,

doi = "10.1016/j.orl.2021.06.015",

language = "English",

volume = "49",

pages = "623--624",

journal = "Operations research letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "4",

}

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 - UT-Hybrid-D

KW - Graphical Traveling Salesperson Problem

KW - Integer programming

KW - Formulation

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

SN - 0167-6377

VL - 49

SP - 623

EP - 624

JO - Operations research letters

JF - Operations research letters

IS - 4

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

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

Cite this