Optimal TSP solutions in VLSI
- In this project, I implemented approaches that perform 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?
The applied approaches utilise graph theory, which means that the set of cities construct an undirected graph. In such graph, cities are represented by graph’s vertices and the distances between them are represented with graph’s edges.
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 1483 points. Nevertheless, due to the fact that the methods applied here result in a fast growth of the computation time, only a fraction of this dataset was used (10-25 points).Link to VLSI dataset
1st Approach: Calculation of all tours
In this first approach, we calculated all possible tours and found the shortest one. Since the time copmlexity of this approach is O(n!), we got the following result for just 10 points.
Figure 1: Optimal tour for 10 points based on the calculation of all tours.
As depicted in Figure 1, we notice that the calculation time has increased extremely fast.
2nd Approach: Calculation of all nor-redundant tours
Since the tour 1->2->3 is equal to the tour 1->3->2, in this second approach, we omitted all non-redundant tours.
Figure 2: Optimal tour for 10 points based on the calculation of all non-redundant tours.
We can clearly see that the calcutation time has significantly improved, by ommitting the redundant tours in our calculations.
3rd Approach: Calculation of optimal tour via Held-Karp algorithm
In this 3rd approach, we utilize the Held-Karp algorithm:
Given a start city A, an end city C, and a set of middle cities Bs, then out of all the possible segments that start in A, end in C, and go through all and only the cities in Bs, only the shortest of those segments could ever be part of an optimal tour.
The time complexity of this algorithm is O(n^2*2^n).
Figure 3: Optimal tour for 10 points based on the Held-Karp algorithm.
The results showed that the Held-Karp algorithm produces the same optimal solutions, but in much faster computation times.
The last part of this project was to test this algorithm in a more complex dataset.
Figure 4: Optimal tour for 18 points based on the Held-Karp algorithm.
Comparison of above approaches
Finally, by comparing the second and the third approaches for an instance of 10 points, the results were:
| Algortihm | Time Complexity | Length | Computation Time |
|---|---|---|---|
| All tours | O(n!) | 81.88 | 3.48 sec |
| Held-Karp algorithm | O(n^2*2^n) | 81.88 | 0.0004 sec |
As we can see, the Held-Karp algorithm significally reduces the computation time. Nevertheless, it still remains time-consuming to be applied in instances of higher than 25 cities.
A more detailed description of this project’s implementation in Python can be seen in this github repository: Link to Github repository