9
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Look for libraries of TSP benchmarks, as studied in OR (e.g. search for works on TSP by Applegate et al., e.g. here)? $\endgroup$ – Neal Young Mar 5 '13 at 21:57
  • 2
    $\begingroup$ There is the TSPLIB with many instances. $\endgroup$ – adrianN Mar 6 '13 at 10:04
  • $\begingroup$ 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. $\endgroup$ – Alejandro Piad Mar 7 '13 at 16:11
  • $\begingroup$ related post: cstheory.stackexchange.com/questions/739/… $\endgroup$ – Neal Young Mar 18 '13 at 16:45
  • 1
    $\begingroup$ @Alejandro, The hidden clique problem might be an example of what you are looking for. Also, you might search for research on what random instances of Satisfiability are considered hard. $\endgroup$ – Neal Young Mar 18 '13 at 16:49
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Alejandro Piad Jun 18 '13 at 14:00
3
$\begingroup$

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.

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

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 hard instances, generated by the community. or create other logical "programs" in SAT.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Alejandro Piad Jun 18 '13 at 14:01
  • 1
    $\begingroup$ @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. 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 $\endgroup$ – vzn Jun 18 '13 at 21:54
  • 1
    $\begingroup$ 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 !!! $\endgroup$ – Alejandro Piad Jun 19 '13 at 23:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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