asadpour_atsp

asadpour_atsp(G, weight='weight', seed=None, source=None)

Returns an approximate solution to the traveling salesman problem.

This approximate solution is one of the best known approximations for the asymmetric traveling salesman problem developed by Asadpour et al, [1]. The algorithm first solves the Held-Karp relaxation to find a lower bound for the weight of the cycle. Next, it constructs an exponential distribution of undirected spanning trees where the probability of an edge being in the tree corresponds to the weight of that edge using a maximum entropy rounding scheme. Next we sample that distribution \(2 \lceil \ln n \rceil\) times and save the minimum sampled tree once the direction of the arcs is added back to the edges. Finally, we augment then short circuit that graph to find the approximate tour for the salesman.

Parameters

Gnx.DiGraph

The graph should be a complete weighted directed graph. The distance between all paris of nodes should be included and the triangle inequality should hold. That is, the direct edge between any two nodes should be the path of least cost.

weightstring, optional (default=”weight”)

Edge data key corresponding to the edge weight. If any edge does not have this attribute the weight is set to 1.

seedinteger, random_state, or None (default)

Indicator of random number generation state. See Randomness.

sourcenode label (default=`None`)

If given, return the cycle starting and ending at the given node.

Returns

cyclelist of nodes

Returns the cycle (list of nodes) that a salesman can follow to minimize the total weight of the trip.

Raises

NetworkXError

If G is not complete or has less than two nodes, the algorithm raises an exception.

NetworkXError

If ‘source` is not None and is not a node in G, the algorithm raises an exception.

NetworkXNotImplemented

If G is an undirected graph.

References

1

A. Asadpour, M. X. Goemans, A. Madry, S. O. Gharan, and A. Saberi, An o(log n/log log n)-approximation algorithm for the asymmetric traveling salesman problem, Operations research, 65 (2017), pp. 1043–1061

Examples

>>> import networkx as nx
>>> import networkx.algorithms.approximation as approx
>>> G = nx.complete_graph(3, create_using=nx.DiGraph)
>>> nx.set_edge_attributes(G, {(0, 1): 2, (1, 2): 2, (2, 0): 2, (0, 2): 1, (2, 1): 1, (1, 0): 1}, "weight")
>>> tour = approx.asadpour_atsp(G,source=0)
>>> tour
[0, 2, 1, 0]