Inverse optimization

This morning Patrick Honner posted the image below on Twitter.

The image was created by Robert Bosch by solving a “traveling salesman” problem, finding a nearly optimal route for passing through 12,000 points.

I find this interesting for a couple reasons.

For one thing, I remember when the traveling salesman problem was considered intractable.

And in theory it still is! But in practice it is not difficult now to find nearly optimal solutions for very large traveling salesman problems.

Another reason I find this interesting is that there is a higher-level problem in the background, the problem of constructing a problem whose solution gives you a desired image.

Going back to efficiency briefly, this means that traveling salesman problems are so easy to solve that one can solve traveling salesman problems inside the inner loop of a larger program that is searching for a problem to solve meeting certain criteria.

Robert Bosch is showing us a solution to two problems.

The image above is the solution to an optimization problem, and the problem it solves is itself the solution to another problem in the background.

He’s doing a sort of inverse optimization, searching for an optimization problem.

He goes into some of his techniques in his recent book Opt Art which I wrote about here.

This gets back to an argument I’ve had with statisticians who are resistant to innovative methods.

They’ll say “But our method is optimal.

You can’t do any better by definition.

End of discussion!” But every method is optimal by some criteria.

The question is whether the method is optimal by criteria appropriate to the problem at had or whether it is only optimal according to criteria that were mathematically convenient at the time it was formulated.

Robert Bosch has shown beautifully that any image can be viewed as the solution to an optimization problem.

Of course the problem has to be crafted for the image.

If he were solving a naturally occurring problem, such as planning a tour for an actual sales rep, and the solution had an uncanny resemblance to a piece of art by Michelangelo, that would be astounding.

More optimization posts Optimization, dominoes, and Frankenstein Traveling salesman art Natural optima occur in the interior.

Leave a Reply