Performance optimization of traveling salesman like issue

Question

I need help optimizing the performance of this, which is essentially similar to the traveling salesman problem, with the addition that I want to make the graph complete first, with the weight of the new edges depending on the distance (it is also crucial for me to pass every node once and just once, which is also why I wanted to make the graph complete so this is easily possible).

Unfortunately, the input graph (undirected/not complete) is quite large with about 10,000 to 100,000 nodes, making my attempt below unusable.

def find_path(G: nx.Graph, start_node: str) -> list:
    # Find the most common weight in the graph
    weights = [data['weight'] for u, v, data in G.edges(data=True)]
    mode_weight = max(set(weights), key=weights.count)

    # Precompute the shortest paths between each node
    shortest_paths = dict(nx.all_pairs_shortest_path_length(G))

    # Make the graph complete, multiply the weight the further away the nodes are from each other
    for node1, paths in shortest_paths.items():
        for node2, path_length in paths.items():
            if node1 != node2:
                new_weight = (path_length - 1) * mode_weight
                if not G.has_edge(node1, node2):
                    G.add_edge(node1, node2, weight=new_weight)

    # Find the best path using christofides algorithm
    return nx.approximation.traveling_salesman.christofides(G, start_node)

Answer 1

memory use

I assume you created a new set in the hopes of reducing your RAM footprint.

    weights = [ ... ]
    mode_weight = max(set(weights), ...)

The first line creates a list with possible dups, where apparently you wanted:

    weights = set( ... )

Also, phrasing like mode_ and "most common weight" is not a good match for max( ... ). Perhaps you'd like to describe the shape of the distribution, so they would be a good match.

random fuzz

                    G.add_edge( ... , weight=new_weight)
                    ...
    return nx.approximation.traveling_salesman.christofides(G, ... )

The edge weights you're adding there are "boring". That is, only a handful of distinct values are being added a very large number of times.

The poor TSP solver will see a large number of identical suboptimal proposed plans.

Recommend you add a small random fuzz to each weight, allowing the solver to immediately discard some obviously inferior trip plans.