Near-Optimal 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?
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
1st Approach: Nearest Neighbour Algorithm
The main idea of this algorithm is quite straightforward:
Start at any city; at each step extend the tour by moving from the previous city to its nearest neighbor that has not yet been visited. Repeat until the starting city is reached.
The time complexity of this algorithm is O(n^2).
Figure 1: Near-optimal tour for 1083 points based on the Nearest Neighbour algorithm.
We notice that the solution for an instance of 1083 cities has been calculated in less than 1 second! But since our results generate some highly redundant moves, let’s try to improve this approach.
2nd Approach: Repeated Nearest Neighbour Algorithm
Nearest Neighbour algorithm can be improved by following this approach:
For each of the cities, run the nearest neighbor algorithm with that city as the starting point, and choose the resulting tour with the shortest total distance.
Figure 2: Near-optimal tour for 1083 points based on the Repeated Nearest Neighbour algorithm.
| Algortihm | Time Complexity | Length | Computation Time |
|---|---|---|---|
| Nearest Neighbour | O(n^2) | 1637.5 | 0.077 sec |
| Repeated Nearest Neighbour | O(n^3) | 1547.0 | 513.75 sec |
We notice that the shortest tour by Repeated Nearest Neighbor Algorithm has been improved in comparison to that of Nearest Neighbor Algorithm with respect to their lengths. Nevertheless, it demands more computation time.
3rd Approach: Sampled Repeated Nearest Neighbor Algorithm
We can modify the Repeated Nearest Neighbor Algorithm so that it can be executed for specific number of cities.
Figure 3: Near-optimal tour for 1083 points based on the Sampled Repeated Nearest Neighbour algorithm.
| Algortihm | Time Complexity | Length | Computation Time |
|---|---|---|---|
| Nearest Neighbour | O(n^2) | 1637.5 | 0.077 sec |
| Repeated Nearest Neighbour for 10 cities | O(n^2) | 1549.4 | 0.616 sec |
| Repeated Nearest Neighbour for 100 cities | O(n^2) | 1547.0 | 6.118 sec |
We notice that we managed to improve the shortest tour with the repeated Nearest Neighbor Algorithm. However, despite the fact that we increased the number of starting cities from 10 to 100, the shortest tour hasn’t significantly improved.
4th Approach: Greedy Algorithm
Another known heuristic algorithm is the Greedy Algorithm: it’s mentioned as Greedy since it greedily adds to the tour the edge that is shortest. Its main steps are presented below:
Maintain a set of segments; intially, each city defines its own 1-city segment. Find the shortest possible edge that connects two endpoints of two different segments, and join those segments with that edge. Repeat until we form a segment that tours all the cities.
The time copmplexity of this algorithm is O(n^2logn).
Figure 4: Near-optimal tour for 1083 points based on the Greedy algorithm.
4th Approach: Altered Greedy Algorithm
At this point, we will try to improve greedy algorithm by swapping segments.
Figure 5: Near-optimal tour for 1483 points based on the Altered Greedy algorithm.
| Algortihm | Time Complexity | Length | Computation Time |
|---|---|---|---|
| Greedy Algorithm | O(n2logn) | 1626.0 | 0.123 sec |
| Altered Greedy Algorithm | O(n2logn) | 1411.8 | 1.373 sec |
Altered Greedy Algorithm generated a shorter tour, but in a higher computation time (1.373 sec).
Comparison of above approaches
| Algortihm | Time Complexity | Length | Computation Time |
|---|---|---|---|
| Nearest Neighbour | O(n2) | 1637.5 | 0.071 sec |
| Repeated Nearest Neighbour for 10 cities | O(n3) | 1549.4 | 0.628 sec |
| Repeated Nearest Neighbour for 100 cities | O(n3) | 1547.0 | 6.13 sec |
| Greedy Algorithm | O(n2logn) | 1602.6 | 0.12 sec |
| Altered Greedy Algorithm | O(n2logn) | 1384.17 | 1.355 sec |
We notice that altered_greedy_tsp resulted in the shortest solution (1384.17), however it required longer time (1.355 secs). On the other hand, nn_tsp was the fastest algorithm (0.071 sec), leading to the longest solution.
By using the above approaches, we managed to find solutions to TSP instances. But, are we sure that these methods will find solutions to every case? Unfortunately no, however, these methods can lead to decent solutions in a reasonable computation time. In another notebook, we will see another method that finds solutions to TSP instances by guaranteeing that the produced results will never be more than a certain value.
A more detailed description of this project’s implementation in Python can be seen in this github repository: Link to Github repository