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.

  • 2
    $\begingroup$ 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. $\endgroup$
    – SamM
    Apr 25, 2013 at 21:24
  • 1
    $\begingroup$ Or the vertices on a single line. $\:$ $\endgroup$
    – user6973
    Apr 25, 2013 at 21:44
  • 4
    $\begingroup$ 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)? $\endgroup$
    – Jeffε
    Apr 26, 2013 at 13:56
  • 1
    $\begingroup$ 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? $\endgroup$
    – Jeffε
    Apr 27, 2013 at 16:56
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Apr 28, 2013 at 6:35

1 Answer 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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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