Lopata Lamps Challenge Meets Bob Bosch

April 2012

 Lopata Lamps Challenge

In March 2012, the Lopata Lamps Challenge was issued via the Washington University Mathematics Department web site to mathematicians worldwide.  See picture to the right.   As results were surveyed, mathematician Robert Bosch from Oberlin came to mind.

"In 2001, I became obsessed with using various mathematical optimization techniques,"  Bob recalls, "mainly linear programming, integer programming, and a host of heuristics to create visual artwork. In 2003, I had an epiphany: I realized the TSP could be used to generate what we now call TSP Art." See [1,2].

Of all the difficult problems in mathematical optimization, the Traveling Salesman Problem (TSP) is the most well known and well studied. A salesman based in one city must visit each city in his sales territory exactly once and then return home. The salesman's goal is to visit the cities in an order that minimizes the total distance he must travel. To generate TSP Art, simply convert a source image into a collection of dots or cities, solve the resulting Traveling Salesman Problem, and connect the dots in the order specified by the optimal tour.

    

TSP Art: Click links for full size erdos20K-TSP, erdos20K-TSP no cities, and erdos 20K-TSP interior.  Step away from the screen to view.

"If you use the Euclidean distance formula to compute edge lengths" Bosch explains, "your TSP will be a geometric TSP, and its optimal tour will be a simple closed curve. The trick is to lay down the dots in such a way that they resemble the source image. Darker sections of the source image should get more dots, and brighter sections should get less dots."

Since 2009, Robert Bosch has been following the Mona Lisa TSP Challenge issued by William Cook from the Georgia Institute of Technology. To meet Cook's challenge, TSP researchers are currently using a series of large-scale art instances to test TSP solution methods.  "The best tour for the 100,000-city Mona Lisa instance has length 5,757,191 and was found by Yuichi Nagata on March 17, 2009," Bosch reports. "On August 1, after 116 days of computation, a lower bound of 5,757,025 was established, yielding a gap of 166 (0.0029%). An optimal solution would set a new world record for the TSP!"

Learn more about TSP Art, visit www.oberlin.edu/math/faculty/bosch/tspart-page.html»

— Math news, stories, videos, and interview by Marie Taris, http://www.math.wustl.edu/marietaris/math.html»

Enjoyed this story? See also March 2012 News story  Art and the Mind Brain at the Kemper»

[1] Bosch, R. and Herman, A., 2004, Continuous line drawings via the Traveling Salesman Problem.  Operations Research Letters 32(4): 302-303.
[2] Kaplan, C.S. and Bosch, R., 2005, TSP art.  In: Proceedings of Bridges 2005: Mathematical Connections in Art, Music, and Science, pp. 301-308.