LKH is a lovely piece of work. I used it a couple of years ago to find a counterexample to an unimportant but fairly long-standing conjecture in combinatorics[0], and the list of scientific applications[1] is impressively diverse.
The best SMT solvers are also hugely impressive. Z3 has an excellent interactive tutorial and online solver.[2]
[0] https://arxiv.org/abs/1408.5108 [1] http://webhotel4.ruc.dk/~keld/research/LKH/ScientificApplica... [2] http://rise4fun.com/z3/tutorial
Angr is a very popular framework which allows for symbolic execution of binaries using Z3 as a backend. It's made a whole class of common CTF challenges almost trivial:
Not to mention the often impressive performance of "general" MIP solvers. It is only a shame that the best ones there are commercial (Gurobi followed by Cplex). That said, Cbc is lovely in a wide range of cases, and is open-source.
It's really basic taxonomy: what sort of problem are we dealing with? If you don't know that, how could you even begin to design a reasonable algorithm for it?
The LKH solver used here has rather impressive performance. From http://webhotel4.ruc.dk/~keld/research/LKH/: "LKH has produced optimal solutions for all solved problems we have been able to obtain," and the studies linked there show that it really does find optimal solutions "with an impressively high frequency."
While the point here is to use an off-the-shelf solver, it can be nice to have visibility into what's actually happening:
- This is a reasonable example for explaining some of the local search TSP heuristics. For instance a "2-opt" move corresponds to picking a contiguous range of columns and flipping them.
- The previous HN post used simulated annealing, which would not be an outright terrible approach to TSP itself -- were it not for the better Lin-Kernighan-based approaches (like LKH).
- If we want, we can tell LKH to start from Sangaline's "nearest-neighbor" approach ("INITIAL_TOUR_ALGORITHM = NEAREST-NEIGHBOR"). This does not make a difference here though.