<p>One general approach to generating harder instances is as follows:</p>

<ul>
<li>Start with a random problem instance.</li>
<li>Embed a "hidden backdoor": randomly choose a good solution (one that's likely to be much better than any solution that already exists) and modify the problem instance to forcibly embed this solution into the problem instance.</li>
</ul>

<p>For instance, for TSP, you could do something like the following.  Generate a random problem instance by picking a random $U(0,1)$ cost matrix.  Then, adjust the problem instance to hide a much-better solution in it: randomly select a tour that visits each vertex exactly once, and reduce the edge weights on that tour (e.g., generate it randomly from $U(0,c)$ where $c&lt;1$; reduce the existing weight; or modify the existing edge with some fixed probability).  This adjustment procedure ensures that the optimal solution will, with high probability, be that special tour that you selected.  If you're lucky and you select a reasonable embedding, it will also not be so easy to recognize where you hid the special solution.</p>

<p>This approach is derived from general ideas in cryptography, where we want to create trapdoor one-way problems: where the problem is hard to solve without knowledge of the secret trapdoor, but with knowledge of the secret trapdoor, the problem becomes very easy.  There have been many attempts to embed secret trapdoors into a variety of hard problems (while still preserving the hardness of the problem even after the trapdoor has been added), with mixed degrees of success.  But this general approach seems like it might workable, for your purposes.</p>

<p>The resulting problem instances might be <em>hard</em>, but will they be <em>interesting</em>, from any practical perspective?  I don't know.  Beats me.  They look fairly artificial to me, but what do I know?</p>

<p>If your primary goal is to select problem instances that are practically relevant and representative of real-world applications of TSP, my suggestion would be take a totally different approach.  Instead, start by surveying real-world applications of TSP, then looking for representative instances of those problems, and convert them to their corresponding TSP problem instance -- so you are working with problem instances derived from a real world problem.</p>

CC BY-SA 3.0
2013-06-18T14:00:00.063Z
I like this approach very much, indeed is very close to what I was trying to come up with, and seems pretty much adaptable to different problems. My initial motivation was making test problems for students, so even though I get the real-word issues, but servers me well for this rather artificial situation (trying to grade student algorithms). In any case, I'll look to adapt it also for my research needs, but that will need a closer look, as you say, to determine if the so created instances are representative enough. Thanks a lot, you got my +1 and acceptance.
Alejandro Piad
CC BY-SA 3.0
2013-06-14T21:43:10.293Z
2013-06-14T21:43:10.293Z
D.W.
<p>an approach that often gives you high control over the nature of solutions is conversion from one NP complete problem to another. now you define "interesting" in your question in a statistical way, but another neat approach is to use classic problems from the field. my favorite is factoring/SAT. it is trivial to find either "smooth" numbers with lots of factors, or prime numbers with only two "factors" (one and the prime). create the SAT instance to solve the factoring, and the solutions are the factors (actually permutations of factors, but also which is not hard to count ahead of time). </p>

<p>under this approach, there is a natural definition of "interesting"—hard instances which cant be solved in P time. and this approach is guaranteed to produce hard instances for factoring non-smooth numbers otherwise it would resolve a foremost open question in complexity theory ie <a href="http://en.wikipedia.org/wiki/Integer_factorization#Difficulty_and_complexity" rel="nofollow noreferrer">hardness of factoring</a>.</p>

<p>then, possibly convert to your problem, in this case TSP. to fill out this answer it would be nice to have a direct SAT to TSP conversion, think they are out there, but am not familiar with them. however, here are some refs on factoring-to-SAT in this question: <a href="https://cs.stackexchange.com/questions/6588/reducing-the-integer-factorization-problem-to-an-np-complete-problem/6605#6605">reducing the integer factorization problem to an NP complete problem</a></p>

<p>if you dont like factoring, it might still be preferrable to create the instances in SAT first for a variety of reasons. you could start with random SAT instances tuned to center in the easy-hard-easy transition point, etcetera. or you could work from <a href="http://dimacs.rutgers.edu/Challenges/" rel="nofollow noreferrer">DIMACS</a> hard instances, generated by the community. or create other logical "programs" in SAT.</p>

CC BY-SA 3.0
2013-06-18T14:01:41.117Z
I like the conversion approach, though you don't provide further links specifically related to TSP, but anyway thanks for the idea, I'll explore it more deeply. You got my +1.
Alejandro Piad
CC BY-SA 3.0
2013-06-18T21:54:02.240Z
@alejandro thx ok heres a link on that. see eg starting at slide 28 here [undergraduate class!], [CMSC 451: SAT, Coloring, Hamiltonian
Cycle, TSP
Slides By: Carl Kingsford](http://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/sat.pdf). converting SAT → Hamiltonian cycle (TSP). there may be more efficient (less overhead) conversion approaches or with other tailored aspects in the literature if that is what is desired. hope to hear further of your work, maybe reply here or on my blog if you like
vzn
CC BY-SA 3.0
2013-06-19T23:34:01.467Z
I checked the pdf, very high level but understandable enough. Although for the time being I got what I need with @D.W. answer, your approach seems very interesting to me. I'll have to try it on my own. I had seen the reduction previously (on a complexity undergraduate course) but hadn't thought on an actual implementation of it specifically for creating hard instances. I have a long term interest in optimization, and metaheuristics, and one of my interest areas are about creating interesting benchmark problems. BTW, just checked you blog, will be coming back for sure !!!
Alejandro Piad
CC BY-SA 3.0
2013-06-16T18:34:40.760Z
2013-06-16T18:40:16.457Z
2017-04-13T12:48:30.830Z
vzn
<p>I'm teaching a course on meta-heuristics and need to generate <em>interesting</em> instances of classic combinatorial problems for the term project. Let's focus on TSP. We are tackling graphs of dimension $200$ and bigger. I tried of course to generate a graph with a cost matrix with values taken from a random $U(0,1)$, and found out that (as expected) the histogram for the path cost (drawn by sampling a lot of random paths) has a very narrow normal distribution ($\mu$ is $~100$ but $\sigma$ is around $4$). This means, in my opinion, that the problem is very easy, since most random paths will be below the average, and the minimum cost path is very close to a random path. </p>

<p>So I tried the following approach: After generating the $U(0,1)$-matrix, take a long random walk around the graph, and randomly (Bernoulli with $p=0.5$) double or halve the value of the edge. This tends to lower all values, eventually reaching zero, but if I take just the right number of steps, I can get a distribution with $\mu$ around $2$ and $\sigma$ around $1$. </p>

<p>My question is, first, is this even a good definition for an <em>interesting</em> problem? Ideally I would want an instance that is highly multi-modal (for the most common neighborhood functions), and that has very few paths near the minimum value, so that most random solutions will be very far from the optimum. The second question is, given this description, how can I generate instances with such characteristics?</p>

CC BY-SA 3.0
2013-03-05T21:57:21.587Z
Look for libraries of TSP benchmarks, as studied in OR (e.g. search for works on TSP by Applegate et al., e.g. [here](http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/))?
Neal Young
CC BY-SA 3.0
2013-03-06T10:04:28.603Z
There is the [TSPLIB](http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/) with many instances.
adrianN
CC BY-SA 3.0
2013-03-07T16:11:57.417Z
Thanks, I checked the link, and its helpful, but my question is about generating instances not because I want to solve a specific instance, but rather because I seek an insight into what makes good combinatorial problems, an insight that can be later extended to other problems besides TSP.
Alejandro Piad
CC BY-SA 3.0
2013-03-18T16:45:01.993Z
related post: http://cstheory.stackexchange.com/questions/739/data-for-testing-graph-algorithms
Neal Young
CC BY-SA 3.0
2013-03-18T16:49:00.217Z
@Alejandro, The [hidden clique problem](https://www.google.com/search?q=hidden+clique+problem&aq=0&oq=hidden+clique&aqs=chrome.1.57j0l3j62.7725&sourceid=chrome&ie=UTF-8) might be an example of what you are looking for.  Also, you might search for research on what [random instances of Satisfiability](https://www.google.com/search?q=random+SAT+threshold&aq=f&oq=random+SAT+threshold&aqs=chrome.0.57j0j62l3.4253&sourceid=chrome&ie=UTF-8) are considered hard.
Neal Young
CC BY-SA 3.0
2013-03-27T15:02:58.293Z
Thanks @NealYoung, specially for the related post link. Many answers there are useful.
Alejandro Piad
<ds.algorithms><co.combinatorics><optimization><tsp><heuristics>
Generating interesting combinatorial optimization problems
Alejandro Piad
# Generating interesting combinatorial optimization problems

(Asked by: username_0 on 2013-03-05)

I'm teaching a course on meta-heuristics and need to generate *interesting* instances of classic combinatorial problems for the term project. Let's focus on TSP. We are tackling graphs of dimension $200$ and bigger. I tried of course to generate a graph with a cost matrix with values taken from a random $U(0,1)$, and found out that (as expected) the histogram for the path cost (drawn by sampling a lot of random paths) has a very narrow normal distribution ($\mu$ is $~100$ but $\sigma$ is around $4$). This means, in my opinion, that the problem is very easy, since most random paths will be below the average, and the minimum cost path is very close to a random path.

So I tried the following approach: After generating the $U(0,1)$-matrix, take a long random walk around the graph, and randomly (Bernoulli with $p=0.5$) double or halve the value of the edge. This tends to lower all values, eventually reaching zero, but if I take just the right number of steps, I can get a distribution with $\mu$ around $2$ and $\sigma$ around $1$.

My question is, first, is this even a good definition for an *interesting* problem? Ideally I would want an instance that is highly multi-modal (for the most common neighborhood functions), and that has very few paths near the minimum value, so that most random solutions will be very far from the optimum. The second question is, given this description, how can I generate instances with such characteristics?

**Tags:** ds.algorithms, co.combinatorics, optimization, tsp, heuristics

> **Comments:**
> **username_1**: Look for libraries of TSP benchmarks, as studied in OR (e.g. search for works on TSP by Applegate et al., e.g. [here](http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/))?  
> **username_2**: There is the [TSPLIB](http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/) with many instances.  
> **username_0**: Thanks, I checked the link, and its helpful, but my question is about generating instances not because I want to solve a specific instance, but rather because I seek an insight into what makes good combinatorial problems, an insight that can be later extended to other problems besides TSP.  
> **username_1**: related post: http://cstheory.stackexchange.com/questions/739/data-for-testing-graph-algorithms  
> **username_1**: @Alejandro, The [hidden clique problem](https://www.google.com/search?q=hidden+clique+problem&aq=0&oq=hidden+clique&aqs=chrome.1.57j0l3j62.7725&sourceid=chrome&ie=UTF-8) might be an example of what you are looking for.  Also, you might search for research on what [random instances of Satisfiability](https://www.google.com/search?q=random+SAT+threshold&aq=f&oq=random+SAT+threshold&aqs=chrome.0.57j0j62l3.4253&sourceid=chrome&ie=UTF-8) are considered hard.  
> **username_0**: Thanks @NealYoung, specially for the related post link. Many answers there are useful.  

---

## 2 answers

### Answer by username_3 on 2013-06-14. Score: 6 | Accepted answer

One general approach to generating harder instances is as follows:

* Start with a random problem instance.
* Embed a "hidden backdoor": randomly choose a good solution (one that's likely to be much better than any solution that already exists) and modify the problem instance to forcibly embed this solution into the problem instance.

For instance, for TSP, you could do something like the following. Generate a random problem instance by picking a random $U(0,1)$ cost matrix. Then, adjust the problem instance to hide a much-better solution in it: randomly select a tour that visits each vertex exactly once, and reduce the edge weights on that tour (e.g., generate it randomly from $U(0,c)$ where $c<1$; reduce the existing weight; or modify the existing edge with some fixed probability). This adjustment procedure ensures that the optimal solution will, with high probability, be that special tour that you selected. If you're lucky and you select a reasonable embedding, it will also not be so easy to recognize where you hid the special solution.

This approach is derived from general ideas in cryptography, where we want to create trapdoor one-way problems: where the problem is hard to solve without knowledge of the secret trapdoor, but with knowledge of the secret trapdoor, the problem becomes very easy. There have been many attempts to embed secret trapdoors into a variety of hard problems (while still preserving the hardness of the problem even after the trapdoor has been added), with mixed degrees of success. But this general approach seems like it might workable, for your purposes.

The resulting problem instances might be *hard*, but will they be *interesting*, from any practical perspective? I don't know. Beats me. They look fairly artificial to me, but what do I know?

If your primary goal is to select problem instances that are practically relevant and representative of real-world applications of TSP, my suggestion would be take a totally different approach. Instead, start by surveying real-world applications of TSP, then looking for representative instances of those problems, and convert them to their corresponding TSP problem instance -- so you are working with problem instances derived from a real world problem.

> **Comments:**
> **username_0**: I like this approach very much, indeed is very close to what I was trying to come up with, and seems pretty much adaptable to different problems. My initial motivation was making test problems for students, so even though I get the real-word issues, but servers me well for this rather artificial situation (trying to grade student algorithms). In any case, I'll look to adapt it also for my research needs, but that will need a closer look, as you say, to determine if the so created instances are representative enough. Thanks a lot, you got my +1 and acceptance.  

---

### Answer by username_4 on 2013-06-16. Score: 3

an approach that often gives you high control over the nature of solutions is conversion from one NP complete problem to another. now you define "interesting" in your question in a statistical way, but another neat approach is to use classic problems from the field. my favorite is factoring/SAT. it is trivial to find either "smooth" numbers with lots of factors, or prime numbers with only two "factors" (one and the prime). create the SAT instance to solve the factoring, and the solutions are the factors (actually permutations of factors, but also which is not hard to count ahead of time).

under this approach, there is a natural definition of "interesting"—hard instances which cant be solved in P time. and this approach is guaranteed to produce hard instances for factoring non-smooth numbers otherwise it would resolve a foremost open question in complexity theory ie [hardness of factoring](http://en.wikipedia.org/wiki/Integer_factorization#Difficulty_and_complexity).

then, possibly convert to your problem, in this case TSP. to fill out this answer it would be nice to have a direct SAT to TSP conversion, think they are out there, but am not familiar with them. however, here are some refs on factoring-to-SAT in this question: [reducing the integer factorization problem to an NP complete problem](https://cs.stackexchange.com/questions/6588/reducing-the-integer-factorization-problem-to-an-np-complete-problem/6605#6605)

if you dont like factoring, it might still be preferrable to create the instances in SAT first for a variety of reasons. you could start with random SAT instances tuned to center in the easy-hard-easy transition point, etcetera. or you could work from [DIMACS](http://dimacs.rutgers.edu/Challenges/) hard instances, generated by the community. or create other logical "programs" in SAT.

> **Comments:**
> **username_0**: I like the conversion approach, though you don't provide further links specifically related to TSP, but anyway thanks for the idea, I'll explore it more deeply. You got my +1.  
> **username_4**: @alejandro thx ok heres a link on that. see eg starting at slide 28 here [undergraduate class!], [CMSC 451: SAT, Coloring, Hamiltonian Cycle, TSP Slides By: Carl Kingsford](http://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/sat.pdf). converting SAT → Hamiltonian cycle (TSP). there may be more efficient (less overhead) conversion approaches or with other tailored aspects in the literature if that is what is desired. hope to hear further of your work, maybe reply here or on my blog if you like  
> **username_0**: I checked the pdf, very high level but understandable enough. Although for the time being I got what I need with @username_3 answer, your approach seems very interesting to me. I'll have to try it on my own. I had seen the reduction previously (on a complexity undergraduate course) but hadn't thought on an actual implementation of it specifically for creating hard instances. I have a long term interest in optimization, and metaheuristics, and one of my interest areas are about creating interesting benchmark problems. BTW, just checked you blog, will be coming back for sure !!!  

---

