<p>If someone is still searching for this, I might give a gist of how I understood that paper:</p>
<ul>
<li>Generate an optimal permutation <span class="math-container">$p$</span> of <span class="math-container">$\{1...n\}$</span>.</li>
<li>Create two random variables, <span class="math-container">$\alpha_i$</span> and <span class="math-container">$\beta_j$</span>, and assign them a random value per each vertex. (Given maximum edge length <span class="math-container">$R$</span>, the maximum value should be around <span class="math-container">$0.1 \cdot R$</span> for <span class="math-container">$\alpha$</span> and <span class="math-container">$0.25 \cdot R$</span> for <span class="math-container">$\beta$</span>) .</li>
<li>An edge <span class="math-container">$d_{ij}$</span> on optimal tour will have exactly the value of <span class="math-container">$\alpha_i + \beta_j$</span>.</li>
<li>For suboptimal tours, the values should be higher (<span class="math-container">$\alpha_i + \beta_j \leq d_{ij}$</span>) But the more subtours you introduce (series of paths where <span class="math-container">$\alpha_i + \beta_j = d_{ij}$</span>), the harder will be to use heuristics.</li>
</ul>

CC BY-SA 4.0
2023-10-28T12:23:21.890Z
2023-10-28T12:23:21.890Z
Ferazhu
<p>Is there a known (polynomial in number of nodes) algorithm to generate TSP instances with known optimal value? </p>

<p>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.</p>

<p>I found the paper <a href="http://www.jstor.org/discover/10.2307/2582378?uid=3737512&amp;uid=2&amp;uid=4&amp;sid=21101132412531" rel="nofollow">Arthur, J. &amp; 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</a>, alas I cannot access it.</p>

CC BY-SA 3.0
2013-04-25T21:24:28.310Z
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
CC BY-SA 3.0
2013-04-26T10:38:11.383Z
touché! added "non-trivial" to the description
AndresQ
CC BY-SA 3.0
2013-04-26T13:56:11.647Z
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ε
CC BY-SA 3.0
2013-04-26T14:38:59.750Z
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
CC BY-SA 3.0
2013-04-26T15:54:58.723Z
in short: is there a polynomial way to generate non-trivial TSP instances with known optimal?
AndresQ
CC BY-SA 3.0
2013-04-26T17:30:44.987Z
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
CC BY-SA 3.0
2013-04-27T00:26:18.150Z
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
CC BY-SA 3.0
2013-04-27T16:56:49.257Z
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ε
CC BY-SA 3.0
2013-04-28T05:41:32.163Z
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
CC BY-SA 3.0
2013-04-28T05:44:09.453Z
Related paper: Stephen A. Cook and David G. Mitchell, ["Finding Hard Instances of the Satisfiability Problem: A Survey"](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.9298), 1997.
Kaveh
CC BY-SA 3.0
2013-04-28T06:35:05.650Z
ps: I still not convinced this question is suitable for cstheory, you may want to read [this](http://meta.cstheory.stackexchange.com/a/2662/). The paper you wrote you have found is the same as the paper in [your previous question](http://cstheory.stackexchange.com/questions/12301/how-to-generate-graphs-with-known-optimal-vertex-cover) 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
<graph-theory><graph-algorithms><tsp>
Generate TSP instances with known optimal
AndresQ
# Generate TSP instances with known optimal

(Asked by: username_0 on 2013-04-25)

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](http://www.jstor.org/discover/10.2307/2582378?uid=3737512&uid=2&uid=4&sid=21101132412531), alas I cannot access it.

**Tags:** graph-theory, graph-algorithms, tsp
> **Comments:**
> **username_1**: 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.  
> **username_0**: touché! added "non-trivial" to the description  
> **username_2**: 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)?  
> **username_0**: 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  
> **username_0**: in short: is there a polynomial way to generate non-trivial TSP instances with known optimal?  
> **username_3**: 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.  
> **username_0**: 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  
> **username_2**: 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?  
> **username_3**: 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.  
> **username_3**: Related paper: Stephen A. Cook and David G. Mitchell, ["Finding Hard Instances of the Satisfiability Problem: A Survey"](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.9298), 1997.  
> **username_3**: ps: I still not convinced this question is suitable for cstheory, you may want to read [this](http://meta.cstheory.stackexchange.com/a/2662/). The paper you wrote you have found is the same as the paper in [your previous question](http://cstheory.stackexchange.com/questions/12301/how-to-generate-graphs-with-known-optimal-vertex-cover) 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.  

---

## 1 answers

### Answer by username_4 on 2023-10-28. Score: 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.


---

