How to solve supposedly intractable problems
johndcook.com
johndcook.com
For a small pearl on problem solving, I recommend "How to solve it"[1], by the great mathematician George Pólya[2]. It teaches you simple techniques you can apply when you are stuck, like "draw a picture", "think about a similar problem you already know the solution for", and "solve a relaxed version of your problem". It all looks pretty much like common sense, but it is not. It's one of those few books I think everyone should read (whenever they are stuck).
[1] http://www.amazon.com/How-Solve-Mathematical-Princeton-Scien...
It seems pretty standard in all it says.
It's probably good to remind people that an NP-complete problem doesn't mean death, but I mean, in real world problems I think that everybody knows what the author is explaining.
I don't even think that he get the point across really well.
Two things:
- there is no emphasis on the fact that we live in a real world, so a solution to an integral at any desired accuracy is definitely enough for non academic studies;
- he forgets to mention that problems like the traveling salesman are for academics. The real world responds to the 'actual computing time of the traveling salesman + the traveling time' problem, i.e., if your exact solution is 10% better than the approximate solution but your computation time is 20 times longer so that the salesman can't even start actually traveling ;-) your best solution becomes suddenly your second best (plus many variations of it).
Of course in general there might be no way to know how much better you could do with the exact solution, but unless there is a Maxwell's devil choosing the set of your towns and roads, it's usually possible to estimate what the average error is (also in terms of some few computed cases and using Monte Carlo techniques). It won't give you the 100% certainty, but it'll give you the certainty that your solution is gonna be not that bad, given how quickly you get it.
I would suggest another thing. When you have a problem that you know it's hard to deal with, give it to a very intelligent person in your team that doesn't know it's very hard to treat. Most likely they will be more creative than you can, because they don't have that sense of hopeless you get when you know that a problem has no exact and easy solution ;-)
I'd say the real world problems are similar to the difference from math and physics according to one of my professors when I was a student. He'd say that when mathematicians and physicists try to approach a problem, their way of trying to find a solution is comparable to two guys approaching a cliff. The mathematician tries to carefully look at every rock and goes down to the ocean very very slowly, the physicist just jumps in an awkward way, kinda scared, screaming and closing their eyes and hoping they won't hit any rocks and that it won't end too bad (they aren't really risking their lives anyhow).
If what you need is a real world solution, you can just jump and see how it goes, you most likely won't die for that (because you are also probably not actually jumping off a cliff).
That doesn't really correspond to the real world problems that TSP occurs in.
While I imagine that variations of TSP occur for logistics companies, it also occurs in problems where "solve once, use many times" applies, such as electronics design.
I'm not super-knowledgeable on either of those two, so I could be wrong, though.
Another point, which is not mentioned in the OP, is about graph problems. A lot of the intractable ones are really intractable only for a (large or infinite) class of degenerate inputs. But on the average case, solving it for "real world" graphs, for a lot of practical applications they can be solved in very reasonable time.
That is true, but it's the same that I was saying (and it's why I included the many variations at the end of the statement). Basically if you have to do something once and for all, then of course you can just solve it in some sort of educated brute force and you are probably fine. It's when you have to continuously adapt the solution to a changing network that you need to be fast, and in that case you need to consider that the computation time kinda together with the traveling time (of course it's more complicated than that and you need to include the cost advantages etc.).
I agree with the graph comment, even if we are growing in the amount of data to deal with those graphs, so there will be often more and more need of simplified or shortened solutions if you want them to run in an app on a phone, or on a server (but for a million requests).
Simply make the distance between cities = "actual computing time of the traveling salesman + the traveling time", and you've got the standard "academic" TSP problem all over again.
An easy example is computing an integral of any function (assuming the integral exists, makes sense, blah blah blah). I can write a solution Monte Carlo style in something like 10 lines of code. It takes me 2 minutes to code and it solves most integrals. Of course, the solution isn't exact, but I can go as far as I want in precision (using a little more code if I want to use optimization methods instead of just brute force). Still, it's pretty fast to write.
Now you can write a program that actually solves the integral exactly, but that takes more time.
Or you can write a program that makes bins and calculates the hight of each bin and computes the integral (not as good, not as fast).
So, if I know I need a solution where I don't care about the forth digit precision, why wouldn't just write the Monte Carlo solution that is superfast?
Although you can try to go back to some academic problems in most cases I don't need an academic solution, so...