Generating interesting combinatorial optimization problems

Question

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?

Answer 1

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.

Answer 2

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.