TSP instances that require exponentially many subtour elimination constraints
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 $n$ vertices, we prove a growth rate of \(\Omega(\phi^n)\), where \(\phi\approx 1.618\) … Read more