TSP Medium Graph Function Exceeding Time Limit – Seeking Optimization Advice”

Error message:
Failed test case: Failed to achieve 85% of success in test cases. Examples of failed tests will be provided.
Expected:
At least 85% of success tsp_medium_graph running below 1.3s and achieving the correct distance,
but got:
Success rate: 0%.

Failed test case: Exceeded time execution limit for a tour starting in node 0. To replicate the graph, you may run generate_graph(nodes = 300, complete = True, seed = 65).
Expected:
tsp_medium_graph method must run in less than 1.3 seconds,
but got:
Time execution exceeded 1.3 seconds.

Failed test case: Exceeded time execution limit for a tour starting in node 0. To replicate the graph, you may run generate_graph(nodes = 300, complete = True, seed = 66).
Expected:
tsp_medium_graph method must run in less than 1.3 seconds,
but got:
Time execution exceeded 1.3 seconds.

Failed test case: Exceeded time execution limit for a tour starting in node 0. To replicate the graph, you may run generate_graph(nodes = 300, complete = True, seed = 67).
Expected:
tsp_medium_graph method must run in less than 1.3 seconds,
but got:
Time execution exceeded 1.3 seconds.

Which algorithms are you using here?

I have asked ChatGPT to suggest more efficient algorithms (Nearest neighbour, simulated annealing, two-opt), and then asked it to improve efficiency of my implementation.

It doesn’t seem to be working just yet, but it’s getting there :slight_smile:

1 Like

You can try to redirect the LLM attention by asking it to find possible bottlenecks in efficiency and fix them.

1 Like

I have tried several implemtations from ChatGPT and Codestral they all have failed either the timelimit or the precision.
ChatGPT has implemented a hybrid approach that combines the Greedy Nearest-Neighbor Algorithm for the initial solution and the 2-Opt Heuristic for improving the tour.
This was not fast enough.
Then I asked for a pure 2-Opt Heuristic which improved the time but was still to slow to pass. The other algorithms have even worse time complexities. Has anyone passed this test?

My unit tests passed after I asked LLM to optimize the code with the requirement mentioned in the problem statement.
It did take multiple follow-ups with LLM.
I used GPT-4o

The individual tests was successful but the grading says it has problems. Any suggestions Thanks in advance