patternMinor
Will the Traveling Salesman Problem (TSP) become easier if the simple path constraint is omitted?
Viewed 0 times
salesmanproblemthetspsimplepathomittedtravelingwillconstraint
Problem
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.
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.
Solution
No, it doesn't become easier. Metric TSP (the version where the distances obey the triangle inequality) is still NP-complete but, in this scenario, the shortest tour always visits every city exactly once. The triangle inequality guarantees that going directly to a new city is always faster than going there via somewhere you've already been.
Context
StackExchange Computer Science Q#76908, answer score: 9
Revisions (0)
No revisions yet.