1

Is there a known (polynomial in number of nodes) algorithm to generate TSP instances with known optimal value?

The idea is to be able to generating arbitrary large instances with known optimal value, in order to be able to test heuristics on them.

I found the paper Arthur, J. & Frendeway, J. Generating Travelling-Salesman Problems with Known Optimal Tours, The Journal of the Operational Research Society, Vol. 39, No. 2 (Feb., 1988), pp. 153-159 for generating TSP with known optimal, alas I cannot access it.

AndresQ
  • 199
  • 9
  • 2
    Yes; put the vertices of the graph in a cycle. Or, easier, create a graph which has no Hamilton path (i.e. with multiple components). I assume you want to exclude such simple counterexamples but you'll have to specify how. – SamM Apr 25 '13 at 21:24
  • 1
    Or the vertices on a single line. $:$ –  Apr 25 '13 at 21:44
  • touché! added "non-trivial" to the description – AndresQ Apr 26 '13 at 10:38
  • 4
    Why do you need a polynomial-time algorithm? Any instances that can be solved by hand in a few minutes can also solve with a computer in a fraction of a second, using the same algorithm you're asking your students to use (presumably brute force). Or are you looking for instances with some special structure (for example: no near-optimal tours)? – Jeffε Apr 26 '13 at 13:56
  • Yes, it's not that I need it to be polynomial, it's just a curiosity (and not to waste precious cpu cycles) of it's possibility.Of course, that the instance is not solvable with a simple heuristic will help as well – AndresQ Apr 26 '13 at 14:38
  • in short: is there a polynomial way to generate non-trivial TSP instances with known optimal? – AndresQ Apr 26 '13 at 15:54
  • Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this. Your question might be suitable for [cs.se] which has a broader scope. – Kaveh Apr 26 '13 at 17:30
  • let's then suppress the "solvable by hand in 5-10 minutes" and assume I want to create TSP instances with thousands of nodes, in polinomial time, and know the optimal solution.

    Bonus points if the optimal solution isn't the solution of the nearest/farthest neighbour heuristic

     – AndresQ Apr 27 '13 at 00:26
  • 1
    Could you please update the original question? Since the problem is trivial otherwise, the question should require that the nearest/farthest neighbor heuristic gives the wrong answer. Also: polynomial in what? What's the input? – Jeffε Apr 27 '13 at 16:56
  • Your question is still suffers from the issue other have stated: in the question you are still missing the word non-trivial and even then you have to define what you mean by non-trivial. Assuming that by non-trivial you mean instances which are "hard" to solve for polynomial-time algorithms, you can pick a polynomial-time computable function that is conjectured to be a cryptographically secure trap-door function and use it in combination with a reduction to the TSP (or any NP-hard problem) to get a hard instance of TSP with a solution. – Kaveh Apr 28 '13 at 05:41
  • Related paper: Stephen A. Cook and David G. Mitchell, "Finding Hard Instances of the Satisfiability Problem: A Survey", 1997. – Kaveh Apr 28 '13 at 05:44
  • 1
    ps: I still not convinced this question is suitable for cstheory, you may want to read this. The paper you wrote you have found is the same as the paper in your previous question from last year, not sure why keep linking to it. Also I don't see why the answer given to your previous question does not work for this new one. – Kaveh Apr 28 '13 at 06:35

1 Answers1

1

If someone is still searching for this, I might give a gist of how I understood that paper:

  • Generate an optimal permutation $p$ of $\{1...n\}$.
  • Create two random variables, $\alpha_i$ and $\beta_j$, and assign them a random value per each vertex. (Given maximum edge length $R$, the maximum value should be around $0.1 \cdot R$ for $\alpha$ and $0.25 \cdot R$ for $\beta$) .
  • An edge $d_{ij}$ on optimal tour will have exactly the value of $\alpha_i + \beta_j$.
  • For suboptimal tours, the values should be higher ($\alpha_i + \beta_j \leq d_{ij}$) But the more subtours you introduce (series of paths where $\alpha_i + \beta_j = d_{ij}$), the harder will be to use heuristics.
Ferazhu
  • 11
  • 1