[Graph] Any interest in adding Nearby Neighbors greedy TSP tour heuristic?
Hi, I wrote the original metric_tsp_approx in BGL a long time ago and had help from Andrew Sutton to make it 'BGL ready'. Given a bit of free time over the holidays, I became interested in making some modifications to the original (various cleanup / better test harness) and then later (after a side track with Christofides TSP heuristic, which I deemed too inefficient for its upper bound benefits) I became interested in implementing a basic LK (Lin-Kernighan) solution. To do so first requires a TSP tour as a starting point. I decided to write an implementation of the greedy Nearby Neighbors heuristic to create this initial tour, which I have done. Nearby Neighbors runs faster than the metric_tsp_approx but has more erratic solution (tour) performance. It also has some different characteristics as a local greedy solution vs. metric_tsp which creates an MST across the whole graph. Is there any interest from the group in taking this heuristic as well as the LK? The LK will perform more slowly than metric_tsp_approx and much more slowly than Nearby Neighbors but also (on average) generate better tours.
On 2026-01-02 00:57, matt.egyhazy--- via Boost wrote:
done. Nearby Neighbors runs faster than the metric_tsp_approx but has more erratic solution (tour) performance. It also has some different characteristics as a local greedy solution vs. metric_tsp which creates an MST across the whole graph.
MST based solutions guarantee maximal factor of 2 as stated: https://www.boost.org/doc/libs/latest/libs/graph/doc/metric_tsp_approx.html BGL contains "10. Maximum Flow and Matching Algorithms" https://www.boost.org/doc/libs/latest/libs/graph/doc/table_of_contents.html Solution based on MST and a minimal matching guarantees maximal factor of 1.5, so would be interesting.
Is there any interest from the group in taking this heuristic as well as the LK? The LK will perform more slowly than metric_tsp_approx and much more slowly than Nearby Neighbors but also (on average) generate better tours.
Would be good to have that option. I moved a simple X11 graphics lib that stopped being updated back in 2007 to github. It contains an interactive LK TSP demo from the original author: https://github.com/Hermann-SW/ezxdisp/blob/main/samples/tsp_LK.c After start pi@raspberrypi5:~/ezxdisp/src/x11 $ ./tsp_LK clicking creates cities of the TSP. With more than 8 cities left click continues input of new cities, right click completes and starts animated LK solution. Perhaps that LK implementation can be helpful to inspect. What BGL functionality would be needed to create similar TSP (X11) graphics demo? Regards, Hermann.
OK, I will cleanup the Nearest (not 'nearby' - whoops)) Neighbor code as much as possible to get it ready for submission as well as my slight modifications to the original metric_tsp_approx code. As a part of this, I also have modification to tree_traits.hpp, graph_concepts.hpp, the test harness (renamed to 'tsp_algo_examples.cpp') which were originally suggested by Andrew but I did not do at the time. I will share via email. Some comments: 1) Christofides approximation algorithm does the 1.5x max solution with MST + min weight perfect matching. It is O(V^3). I would prefer to write faster algorithm/heuristic that scales better. I will perhaps look into Christofides and/or LK after I finish the greedy Nearest Neighbor. 2) Thank you, I step through your implementation. 3) Besides graphviz (which is not interactive), I am not aware of a built-in way of creating an interactive UI like you describe. I see no reason why it couldn't be used with UI code separately though, seems very straight forward. Simply separate the UI and the graph code in a encapsulated way. Can probably be done with metric_tsp_approx as-is.
On 2026-01-02 13:44, matt.egyhazy--- via Boost wrote:
Some comments:
1) Christofides approximation algorithm does the 1.5x max solution with MST + min weight perfect matching. It is O(V^3). I would prefer to write faster algorithm/heuristic that scales better. I will perhaps look into Christofides and/or LK after I finish the greedy Nearest Neighbor.
Good. I will resume my efforts to solve 100,000 cities mona-lisa100K.tsp with 1,000USD prize money https://www.math.uwaterloo.ca/tsp/data/ml/monalisa.html on semester break mid February (age 60): https://github.com/Hermann-SW/RR I use Ruin and Recreate principle, next essential step is parallelization (either with OpenMP on my 192 core 8-socket server or with HIP and my AMD Instinct MI50 GPUs).
2) Thank you, I step through your implementation.
Not my implementation, but that of original author Morihiko Tamai. I linked to his work in ezxdisp repo README.
3) Besides graphviz (which is not interactive), I am not aware of a built-in way of creating an interactive UI like you describe. I see no reason why it couldn't be used with UI code separately though, seems very straight forward. Simply separate the UI and the graph code in a encapsulated way. Can probably be done with metric_tsp_approx as-is.
You are right, will be a good exercise to replace LK TSP code in ezxdisp example and use metric_tsp_approx instead. Regards, Hermann.
participants (2)
-
hermann＠stamm-wilbrandt.de -
matt.egyhazy＠gmail.com