I am happy to announce that our paper “The Dantzig–Fulkerson–Johnson TSP formulation is easy to solve for few subtour constraints”, co-authored with Austin Buchanan, has been accepted at INFORMS Journal on Optimization!

In this work, we investigate one of the most successful approaches used for the TSP: The Dantzig, Fulkerson, and Johnson (DFJ) formulation. Although this model has exponentially many subtour elimination constraints (SECs), it has been observed that relatively few of them are needed to prove optimality in practice. This leads us to wonder: What is the complexity of the DFJ model when just a small number of SECs are imposed? Also, for a given instance, what is the minimum number of SECs required to certify the optimality of one of its TSP tours? We offer both positive and negative results. On the positive side, we give an algorithm to solve the DFJ model that runs in polynomial time when only a constant number of SECs are imposed. With an additional condition, we also find a minimum number of SECs in polynomial time. This provides an explanation for the apparent easiness of some TSP instances despite the intractability of the problem in the worst case. As part of our experiments, we show that the original 49-city TSP instance of DFJ requires a minimum of four SECs, which we generate in a fraction of a second with a simple Python implementation.