English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

The Graphical Traveling Salesperson Problem (GTSP) is the problem ofassigning, 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 arespanning, connected and Eulerian. Naturally, known mixed-integer programmingformulations use integer variables $x_e$ in addition to others. Denis Naddefposed the challenge of finding a (reasonably simple) mixed-integer programmingformulation that has integrality constraints only on these edge variables.Recently, Carr and Simonetti (IPCO 2021) showed that such a formulation cannotconsist of polynomial-time certifyiable inequality classes unless$\mathsf{NP}=\mathsf{coNP}$. In this note we establish a more rigorous result,namely that no such MIP formulation exists at all.

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