# Generate TSP instances with known optimal

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.

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

• 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.