4 ms·
For context, the tests here are performed on 50- and 100-city instances, as they are limited by current GPU memory sizes. Meanwhile, the best heuristic code for
by thxg 6y ago
For context, the tests here are performed on 50- and 100-city instances, as they are limited by current GPU memory sizes. Meanwhile, the best heuristic code for TSP [1] frequently provides optimal solutions to 100k-city instances ("heuristic" = no optimality guarantee, like what this paper proposes; but one can then seek a proof of optimality if desired using a slower "exact" algorithm).
Also, Dantzig, Fulkerson and Johnson solved a 50-city TSP to optimality, with an exact method, by hand, in 1954 [2]. The practical running time was slower than what is proposed here, admittedly :-).
This is not a criticism of the paper, though: To their credit, the authors are quite straightforward about this, they're not trying to hide it. Their point is to demonstrate that their machine learning approach has potential.
[1] http://webhotel4.ruc.dk/~keld/research/LKH/ http://webhotel4.ruc.dk/~keld/research/LKH/
[2] http://www.math.uwaterloo.ca/tsp/uk/history.html http://www.math.uwaterloo.ca/tsp/uk/history.html
- algo_trader 6y ago> best heuristic code for TSP .. 100k-city instances These "best cases" are hand-tuned for the domain by algorithm experts - right? How big is the performance jump from generic z3 or whatever? Edit: After alphazero, there was lots of chatter about improving combinatorical problems. This has proven elusive.
- bopbeepboop 6y agoMy impression of Alpha Zero research is that given enough feedback, AI would find “good” routes in the sense of sensible driving, minimal lefts, nearby bathrooms, etc — but not that it had anything in particular to say about hard combinatorics. Ie, AI would find “fast” routes in the sense of “a human driving these gets done fast, all things considered” but not necessarily “fast” in a simple combinatorics problem — which is actually good, because simple combinatorics often fails in the real world (eg, longer routes without left turns are faster). Did I miss something about how this more directly applies to combinatorics?
- algo_trader 6y agoCombinatorics (and AZ) can have unlimited self-play (i.e. search) with precise reward. This is quite rare in most real world problems. I dont really have a strong intuition for mathematics. It is possible that nets are simply good with spatial boards and not good enough with arbitrary graphs.
- thxg 6y ago> These "best cases" are hand-tuned for the domain by algorithm experts - right? Correct. It is arguably more than just "hand-tuned". The algorithm I mentioned, LKH, was entirely designed for TSP, and I'm not aware of it being applicable to much else. > How big is the performance jump from generic z3 or whatever? For TSP, an enormous jump. Certainly more than 3 orders of magnitude.
- alfiedotwtf 6y agoProvably optimal? I thought TSP was NP-Hard and could only ever be solved via heuristics
- gopiandcode 6y agoNP-hard refers to solving the problem in the general case - for a given specific instance it may be possible to find an optimal solution more easily by exploiting specific features of the graph (for instance, a series of nodes arranged in a ring would have a trivial optimal solution).