Will the Traveling Salesman Problem (TSP) become easier if the simple path constraint is omitted?
That is, each node in the topological graph should be visited once at least (instead of exactly).
Is it still NP-complete or reduced to a P problem?
How would this modification affect classical methods for solving the original TSP such as dynamic programming, mixed integer programming, meta-heuristics and maybe branch-and-cut/bound/price?
What I have tried:
I believe this variant might be easier to solve, but after a sketchy thought about the MIP model, I found it is hard to write the sub-tour elimination constraints.
I have checked TSP Where Vertices Can be Visited Multiple Times but it is asking for a working solution which could be a heuristic that does not guarantee the optimality and computational time. This is not what I want.