|
| Photo from Bell Labs News, March 3, 1986 |
Reseachers at Bell Labs in the mid-1980s developed a developed a technique for the quick production of customized computer chips. This LaserLogic method is described in a Bell Labs News article from March 3, 1986.
| "A LaserLogic chip starts with many simple logic gates that are connected to each other. A laser then scissors this network of gates into many individual circuits by vaporizing---or `shooting'--- thousands of special interconnections called laser links. The final configuration of the circuit is determined by which links are shot." (Joel Rosenkrantz, Bell Labs News, March 3, 1986) |
The TSP in this application is to minimize the total travel time of the laser, as it moves between the interconnections to be cut. The cities correspond to the locations of the interconnections, and the travel cost between two cities is the time to move from one interconnection point to the other interconnection point. The solution provides the order in which the laser cuts the necessary interconnections.
|
|
| Photo from Bell Labs News, March 3, 1986 |
David S. Johnson, a top computer scientist at ATT Research, collected data sets from three LaserLogic chips and contributed them to Gerd Reinelt's TSPLIB in June of 1991. Johnson was at the time working at Bell Labs, and the application matched his own interest in heuristic methods for large-scale TSPs. A short article in the Mathematical Programming Society newsletter Optima contains some remarks by Johnson concerning this work.
The three contibuted examples have 7397, 33810, and 85900 ciites, respectively. They are denoted as pla7397, pla33810, and pla85900; the last two are the largest problems in the TSPLIB collection.
In these examples, travel costs are modeled as the Euclidean distance (rounded up to the nearest integer value) between city locations.