It is possible that the tsp_medium_graph grader is broken?

So I was getting the errors mentioned in a different topic about suboptimal performance, but now I’m just getting:

There was an error grading your submission. Details:
'str' object has no attribute 'args'

The test, however, passes for unittests.test_tsp_medium_graph(Graph_Advanced)

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.

I was passed but… still graded Fail…

Passed • 75/100 points

Cant attach image here.

You can’t attach images until you have enough forum posts to earn some amount of trust on the platform.

1 Like

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:

  1. 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.
  2. 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.
  3. 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.
  4. 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

Ok later I try, seriously Gen AI still not up to par yet. Only 1 year plus old.

I find the coding stuff more for Comp Science background required to read, understand and troubleshooting the codes. For all 3 courses.

It reminds of Uni Colorado Boulder Data Structures and Algorithms specialisation in Coursera.

I understand that the grader for tsp_medium_graph() was updated yesterday to fix an issue (as reported in some other threads).

Thank you all for your inputs, I will investigate it. As soon as I have an answer I get back to you.

1 Like

Hi @Bernard_Leong,

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?

Thanks,
Lucas

Sorry, I didn’t save it

nevermind, I re-opened it and the code seems to be there

A question to clarify:

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.
“”"

Which is correct? 100 nodes or 300 nodes? Thanks.

Hi Lucas,

Thank you for your note. I have sent you the notebook privately.
Bernard

For visibility,

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.

Thanks for flagging this! It is actually 300 nodes. The text is fixed.

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?

Possibly you zapped the metadata that tells the grader to pay attention to the cell that contains that function.