What we can learn from the traveling salesman?

For those that have worked in the area of operations research, mathematics or computer science the traveling salesman is an intriguing and well known problem. The problem sounds very easy, what is the shortest route traveling from one destination to the next and returning to the place you started. What makes this problem intriguing is that no mathematical algorithm exists that guarantees the shortest route in an acceptable amount of time (to be precise: it’s an NP-Complete problem and as such the most efficient algorithm to date – and probably forever – solves the problem in a time that increases exponentially with the number of cities).  In practice this means that normal CPU’s would need days  or even years to solve problems with a relatively small number of cities (e.g. 100).

Applying marketing data includes many optimizations for which we can prove that no efficient algorithm exists. Examples are television reach optimizers or allocating inventory towards brands. For these problems, as a real optimal solution cannot be guaranteed, mathematicians need to develop heuristic algorithms; an algorithm that tries to get to the best possible solution in a limited amount of time.

And that brings me to the key subject of this blog. The deflation I’ve seen on what it means to optimize. Ten years ago, my clients asked me about how our optimization techniques work; they even got independent mathematicians to audit our methods. Nowadays this doesn’t happen anymore. To have a button in software that says “optimization” seems to be enough to convince prospects. And this is a slippery slope as some optimization routines I’ve seen has moved towards simply users clicking (with some basic information) what they think is best. And let me guarantee, users are not able to optimize as good as good old-fashioned mathematical optimization techniques.

Don’t believe me, please download a little piece of software I wrote many, many years ago. This software allows you to try and find the best route for a traveling salesman before the computer gives it a go. With about 40 cities, on average – in my case – the computer does 8 to 10% better. That’s a lot if it is a 10 mln dollar decision!

And yes, as the computer algorithm cannot guarantee the best solution, you might be able to beat the algorithm. Do let me know (with screenshot!) if you’ve been able to do this.