held_karp_ascent(G, weight='weight')
Solves the Held-Karp relaxation of the input complete digraph and scales the output solution for use in the Asadpour ASTP algorithm.
The Held-Karp relaxation defines the lower bound for solutions to the ATSP, although it does return a fractional solution. This is used in the Asadpour algorithm as an initial solution which is later rounded to a integral tree within the spanning tree polytopes. This function solves the relaxation with the branch and bound method in .
The graph should be a complete weighted directed graph. The distance between all paris of nodes should be included.
Edge data key corresponding to the edge weight. If any edge does not have this attribute the weight is set to 1.
The cost for the optimal solution to the Held-Karp relaxation
A symmetrized and scaled version of the optimal solution to the Held-Karp relaxation for use in the Asadpour algorithm.
If an integral solution is found, then that is an optimal solution for the ATSP problem and that is returned instead.
Minimizes the Held-Karp relaxation of the TSP for G
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them