Guaranteed TSP solutions in VLSI
- In this project, I implemented approaches that perform near-optimal combination of MOS transistors onto Integrated circuits, a process called Very Large Scale Inegration (VLSI). The process of VLSI was examined by using approaches of the known combinatorial optimization problem called Traveling Salesperson Problem (TSP). TSP is described as follows:
Given a set of cities and the distance between each pair of cities, what is the shortest possible tour that visits each city exactly once, and returns to the starting city?
in the project about the near-optimal solutions TSP VLSI instances, we examine some approaches which can lead to near-optimal solutions with instances of much larger number of cities (>100). However, we noticed that these methods cannot guarantee that the generated solutions will never be longer than a certain tour length. In this project, we will examine one method that produces solutions to TSP instances which are guaranteed to be no more than as a specific tour.
Prim’s Minimum Spanning Tree
The main idea of this algorithm is the below:
List all the edges and sort them, shortest first. Initialize a tree to be a single root city (we’ll arbitrarily shoose the first city). Now repeat the following until the tree contains all the cities: find the shortest edge that links a city (A) that is in the tree to a city (B) that is not yet in the tree, and add B to the list of A’s children in the tree.
Parameters
The parameters that have been taken into account are the total distance of the process by starting and ending at one point and visiting all other points exactly once and the time of the computation.
Dataset
The dataset used in this project consists of 1083 points.Link to VLSI dataset
As a first step, let’s create one minimum spanning tree for the imported dataset.
Figure 1: Minimum spanning tree of imported dataset.
Turning a Minimum Spanning Tree into a Tour
In the above section, we manage to create one minimum spanning tree. Now, let’s convert this method to the generation of a tour that is no longer than twice as long as the minimum spanning tree.
Figure 2: Near-optimal tour for 1083 points based on Minimum spanning tree algorithm.
Altered MST
At this section, let’s try to improve the performance of the above approach in order to find better solutions. More specifically, we will implement the reversing of graph’s segments.
Figure 3: Near-optimal tour for 1083 points based on Altered Minimum spanning tree algorithm.
Comparison of above approaches
| Algortihm | Time Complexity | Number of Cities | Length | Computation Time |
|---|---|---|---|---|
| Prim’s Minimum Spanning Tree | O((V + E)logV)) | 1083 | 4961.402 | 1.32 sec |
| Altered Prim’s Minimum Spanning Tree | O((V + E)logV)) | 1083 | 3911.065 | 16.023 sec |
We conclude that Altered Prim’s Minimum Spanning Tree resulted in better results, but demanded higher computation time. We should not forget, however, that both approaches generate solutions that are guaranteed to be no longer than twice as long as the minimum tour.
A more detailed description of this project’s implementation in Python can be seen in this github repository: Link to Github repository