betaFeedback

WorksComputer Science

TSP instances that require exponentially many subtour elimination constraints

Abstract

We construct pathological TSP instances that require exponentially many subtour elimination constraints (SECs) in the sense that, if a smaller collection of SECs is imposed, then the Dantzig-Fulkerson-Johnson model returns a disconnected solution costing less than an optimal tour. For asymmetric instances on nn vertices, we prove a growth rate of Ω(ϕn)Ω(ϕ^n), where ϕ≈1.618ϕ\approx 1.618 is the golden ratio. A node-splitting reduction gives metric instances with Ω(ϕn/2)Ω(ϕ^{n/2}) growth. We also give instances in the plane under the Euclidean, Rectilinear, and Maximum metrics that require exponentially many SECs. Concorde struggles on them, with solve times growing exponentially despite tiny integrality gaps.

Paper details

vlnc:W_ch4aanrp
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC-BY-NC-ND-4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude, GitHub Copilot

View statement
Looking for related papers…