2
$\begingroup$

I am trying to devise an algorithm in which given the length of a path that satisfies the constraints of the Traveling Salesman Problem, I can find the path. Currently, my only solution is to find a cost matrix of every possible path and brute force adding them up until I get a solution that equals the length of the path.

Is there a better way to find a TSP path given the length?

$\endgroup$
0
$\begingroup$

This decision problem ("does this graph contain a tour of length at most this?") is NP-complete, so you won't find a polynomial-time algorithm most likely.

In addition to the brute-force method you describe, you can have a look at Held-Karp, which solves the problem in $O^*(2^n)$ time using dynamic programming. For an even more practical solution, you can have a look at the Concorde TSP solver, which has been successfully used to solve instances with tens of thousands of cities optimally.

$\endgroup$
  • $\begingroup$ Concorde works great, thank you. I’m currently looking at a problem of about 250,000 nodes, and Concorde doesn’t do as well as the optimal path even after tens of millions of iterations. I know the length of the optimal path, so that’s where this question came from. $\endgroup$ – Matthew Anderson Nov 30 '18 at 17:57
  • 1
    $\begingroup$ The problem is not "length at most this" but "length exactly this". However, it's still NP-hard because Hamiltonian Cycle can be reduced to it. $\endgroup$ – Albert Hendriks Dec 30 '18 at 23:22
0
$\begingroup$

The additional information can be used by changing the usual LP model to one with an additional constraint that requires the total length to be equal to the known path length (or for numerical safety, bracketed tightly from both sides but not demanding exact equality). This will still result in fractional solutions, but they can be dealt with as usual. Also the overall search is just for the first integral solution, so the tree search (if any) is small, only used as a fallback for when the cut-generation algorithms fail to find any cut while the solution is still fractional, and quickly pruned when it tries a bad guess (as this quickly results in infeasibility of the LP model).

In a quick informal test on an instance with 51 cities this helped significantly (finding the result in under 3k simplex pivots vs 13k for solving the same instance normally), but I am comparing my own bad solver against a quick modification of it, which either way does not use any fancy cuts so likely it makes the difference more pronounced than it should be.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.