I encountered that issue a few times, but was able to ignore it and it eventually went away as I worked through the four functions. Maybe the process of solving the problems helped to fix it, not sure.

Hi everyone, I suspect the tsp_medium_graph grader is broken. I am going to live with the 75% and I passed the whole course with 100% except for this. The error is the same despite the fact that I have tried many methods of optimizations:

Reduced Start Points for Nearest Neighbor: I tried reducing the number of parallel nearest neighbour searches to 3, which mitigates between exploration and time efficiency.

Limited 2-Opt Iterations: The maximum number of iterations for 2-opt has been reduced to 50, down from 100. Each iteration performs only 5 random edge swaps to keep the computation lightweight. I tested the generate graphs at least a few times with the errors out but the speed is ok.

Randomized Batching in 2-Opt: Instead of checking every possible pair of edges during 2-opt, the algorithm now selects 5 random pairs of edges per iteration. This greatly reduces the computation time while still allowing significant improvements.

Early Stopping: The 2-opt optimization exits early if no improvement is detected after an iteration. This saves time by avoiding unnecessary iterations when the solution is already near optimal.

I am sharing my code here and everyone can decide on why my code did not work against the unit test.

def tsp_medium_graph(self, start_vertex: int) -> tuple[float, list[int]]:
"""
Solve the Traveling Salesman Problem for medium (~300 node) graphs. The goal is to improve
upon the nearest neighbor solution using 2-opt optimization, executing in less than 1.3 seconds.
This version runs the nearest neighbor search from multiple start points in parallel.
"""
# Precompute edge weights for faster lookup
vertices = list(self.graph.keys())
n = len(vertices)
edge_weights = {(i, j): self._get_edge_weight(vertices[i], vertices[j]) for i in range(n) for j in range(n) if i != j}
# Nearest neighbor heuristic for a single start point
def nearest_neighbor(start: int):
path = [start]
unvisited = set(vertices)
unvisited.remove(start)
total_distance = 0
current = start
while unvisited:
next_vertex = min(unvisited, key=lambda vertex: edge_weights.get((current, vertex), float('inf')))
total_distance += edge_weights.get((current, next_vertex), float('inf'))
path.append(next_vertex)
unvisited.remove(next_vertex)
current = next_vertex
total_distance += edge_weights.get((current, start), float('inf')) # Return to start
path.append(start)
return total_distance, path
# Run nearest neighbor from 3 different start points in parallel
start_points = random.sample(vertices, 3) # Try 3 different starting points to save time
results = Parallel(n_jobs=-1)(delayed(nearest_neighbor)(start) for start in start_points)
# Select the best nearest neighbor solution
best_distance, best_path = min(results, key=lambda x: x[0])
# Apply 2-opt optimization to improve the solution
def two_opt(route: list[int], max_iterations: int = 50) -> list[int]:
best = route
iterations = 0
improved = True
while improved and iterations < max_iterations:
iterations += 1
improved = False
# Batch random edge swaps rather than checking all pairs
for _ in range(5): # Limit to 5 random swaps per iteration
i, j = sorted(random.sample(range(1, len(route) - 1), 2))
if j - i == 1: continue # Skip adjacent nodes
new_route = route[:i] + route[i:j][::-1] + route[j:]
if self._tour_cost(new_route) < self._tour_cost(best):
best = new_route
improved = True
if not improved:
break # Early exit if no improvement
return best
# Perform 2-opt optimization on the best nearest neighbor result
optimized_path = two_opt(best_path, max_iterations=50) # Further reduced iterations for speed
optimized_dist = self._tour_cost(optimized_path)
return optimized_dist, optimized_path
# Helper function to calculate the total cost of a given tour
def _tour_cost(self, path: list[int]) -> float:
"""
Helper function to calculate the total cost of a given tour.
"""
total_distance = 0
for i in range(len(path) - 1):
total_distance += self._get_edge_weight(path[i], path[i+1])
return total_distance

There is a couple of issues with your code. I see that you import joblib, using Parallel and delayed functions, this is not allowed in this assignment, you should stick with the libraries that are lodade in the assignment. This is crucial as the autograder loads the library prior to parsing your solution, so any other library will break the autograder. Also, it looks like you have added some new attributes to the Graph class, which should not be done. I will improve the language in the assignment in this way.

That said, could you please send me your notebook privately? I would like to take a look. Thanks!

@Peter_Litvak, could you also send me your notebook?

5.4 Test Exercise 4 (method Graph_Advanced.tsp_medium_graph)

Run the code below to test the tsp_medium_graph on complete (fully connected) graphs with 300 nodes. The requirements for passing this exercise are:

The tsp_medium_graph comment wrote:

“”"
Solve the Travelling Salesman Problem for a medium (~100 node) complete graph starting from a specified node.
Expected to perform better than tsp_large_graph. Must run under 1 second.

Parameters:
start: The starting node.

Returns:
A tuple containing the total distance of the tour and a list of nodes representing the tour path.
“”"

Some errors were caused by importing joblib to the solution, which should not be done. In fact it shouldn’t be imported any library rather than the ones contained in the notebook. I will improve the text to advise learners to do so.

I am having trouble with this, too. My intuition wants me to think I messed up the “Your code here” tag for the tsp_medium_graph" because my code passes until the last unitest. At this point I get the following:

`Failed test case: Your Graph class does not contain a method called tsp_medium_graph.
Expected: A Graph with a method called tsp_medium_graph
Got: No tsp_medium_graph method detected`

that is kind of telling since there is definitely an instance of code for this method … is there something we can reset to make sure there is a valid test?