My friend and co-author Bob Bosch was awarded First Prize in the Mathematical Art Exhibition held by the American Mathematical Society. This work was based on the Traveling Salesman Problem:
He describes his work in the exhibition catalog: “I began by converting a drawing of a two-component link into a symmetric collection of points. By treating the points as the cities of a Traveling Salesman Problem and adding constraints that forced the salesman’s tour to be symmetric, I constructed a symmetric simple-closed curve that divides the plane into two pieces: inside and outside. With a water jet cutter, I cut along this Jordan curve through quarter-inch thick, six-inch diameter disks of steel and brass. By swapping inside pieces I obtained two copies of the sculpture. Here, steel is inside and brass is outside… After I get an idea for a piece, I translate the idea into a mathematical optimization problem. I then solve the problem, render the solution, and see if I’m pleased with the result. If I am, I stop. If not, I revise the mathematical optimization problem, solve it, render its solution, and examine it. Often, I need to go through many iterations to end up with a piece that pleases me. I do this out of a love of mathematical optimization–the theory, the algorithms, the numerous applications.”
If you have a spare hour or two, be sure to check out the complete exhibition. Hmmm.. I have had some thoughts about translating my baseball schedules into Lego. I wonder if that could compete? Maybe not.
I am the proud owner of two Boschs: I received a copy of a domino portrait of myself (I periodically use the portrait as my photo). I also have a spectacular traveling salesman art based on work by Warhol. If you visit my office, I have placed it so it is seen at the end of a long hallway. It is a conversation piece for all the hallway residents. You can get your own Bosch at Domino Artwork. There are also instructions for teachers who want to make a domino portrait of Barack Obama, Abe Lincoln, Martin Luther King, and others as classroom projects.
Thanks to Twitter’s @wjcook (Georgia Tech’s TSP guru Bill Cook) for the pointer.
This weekend I was looking at one of the most famous problems in computer science, the Traveling Salesman Problem (TSP). If you have a map of cities, and the distances between them, the goal is to start at one city, and then visit each city exactly once covering the shortest distance possible. The problem is NP-complete, meaning there is no way to find the best solution without trying all possible solutions. And the number of possible solutions is huge for even a small number of cities. For example if there are 5 cities, numbered 0 through 4, then one possible solution would be {0, 4, 3, 1, 2} (where I haven’t specified the distances between cities). There would be a total of 5! = 120 total possible solutions here, not taking into account duplicates. The possible solution {4, 3, 1, 2, 0} would be equivalent to {0, 4, 3, 1, 2}, and in general each solution has n equivalent solutions, so the total number of distinct possible solutions for the Traveling Salesman Problem is (n-1)! which is still gigantic. If there are just 40 cities, there are 39! = 20,397,882,081,197,443,358,640,281,739,902,897,356,800,000,000 possible solutions. Anyway, I have been experimenting with a Simulated Bee Colony algorithm to try and solve some TSP sets. The idea is to mimic the behavior of a colony of bees to find a very good but not necessarily optimal solution. I haven’t been too successful so far. For one standard TSP benchmark problem set with 51 cities (problem “eil51.tsp”), the optimal shortest path solution is known to be 426 arbitrary units of distance long. My current version of a Simulated Bee Colony Algorithm is stalling out with a best solution / shortest distance found of about 720. See screenshot below. But I’m going to keep at it. I suspect that my Simulated Bee Colony algorithm, like many related meta-heuristic algorithms including Genetic Algorithms, Ant Colony Optimization, and Simulated Annealing Algorithms, is prematurely converging. So, I’m writing some analysis code to see if I can gain some insights into what’s going on.