Traveling salesman problem can be cast to an integer program, see https://gurobi.github.io/modeling-examples/traveling_salesman/tsp.html. The problem is, however, that the solution might contain unwanted cycles. A strategy to avoid those cycles is to check the solution for cycles. If the solution contains cycles, they are added as a constraint to the integer program. Then you rerun your solver with the new constraints included until you eventually obtain a cycle-free solution. I believe this concept is referred to as "lazy constraints", callbacks, or column generation.
I stumbled across this document by Cohen https://hal.inria.fr/inria-00504914v2/ which avoids re-running your solver over and over again by adding $O(n)$ anti-cycles constraints. The key observation is that the maximum average degree of subgraphs is bound. Therefore Cohen adds linear constraints in the form
- Each edge sends out a flow of 2 if it is taken
- Vertices receive a flow of strictly less than 2
preventing a solution from having cycles.
I find Cohen's approach elegant, because you create your integer program once, run it once, and get a solution. However, I am just a user of integer programming.
I would like to ask what experts think of Cohen's approach. To my surprise, the paper is not cited very much. Those who use it, seem happy. In fact, for my task, Cohen's approach is absolutely robust, so far, and I am happy with the solutions. However, I have not yet compared them to the solutions I'd get with the lazy-constraints approach.