When I read Transformer I thought this was some sort of electrical circuit based solution. I wonder if you could get some sort of solution by representing the network as an electrical circuit.
The Transformer Network for the Traveling Salesman Problem
11–20 of 22 posts
Re: The Transformer Network for the Traveling Salesman Problem
#12When I read Transformer I thought this was some sort of electrical circuit based solution. I wonder if you could get some sort of solution by representing the network as an electrical circuit.
You could try it on a quantum computer, but you'll have to wait a decade (at least) the see one with enough bits to solve a problem of practical size ;-)
Re: The Transformer Network for the Traveling Salesman Problem
#13I believe that AI cannot solve this problem by generating a better algorithm. The only algorithm that will give the most optimal result is brute force, trying every possible combination. Any form of deep learning will only do as well as it gets closer to that, and require just as much computation. The advent of working quantum computers and other hardware gains will be the only solution. There is no software that can solve the traveling salesman problem, nor will there ever be, without much better hardware.
Re: The Transformer Network for the Traveling Salesman Problem
#14When I read Transformer I thought this was some sort of electrical circuit based solution. I wonder if you could get some sort of solution by representing the network as an electrical circuit.
You could try it on a quantum computer, but you'll have to wait a decade (at least) the see one with enough bits to solve a problem of practical size ;-)
You can build an analogue simulator for TSP by exploiting the properties of the path integral.
Re: The Transformer Network for the Traveling Salesman Problem
#15For 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…
> 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.
My 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?
Re: The Transformer Network for the Traveling Salesman Problem
#16When I read Transformer I thought this was some sort of electrical circuit based solution. I wonder if you could get some sort of solution by representing the network as an electrical circuit.
You could try it on a quantum computer, but you'll have to wait a decade (at least) the see one with enough bits to solve a problem of practical size ;-)
We do not have reasons to believe that a quantum computer would be much better than classical for this class of problems.
Re: The Transformer Network for the Traveling Salesman Problem
#17I believe that AI cannot solve this problem by generating a better algorithm. The only algorithm that will give the most optimal result is brute force, trying every possible combination. Any form of deep learning will only do as well as it gets closer to that, and require just as much computation. The advent of working quantum computers and other hardware gains will be the only solution. There is no software that can…
I mentioned this in another thread: currently we do not have reasons to believe quantum computers are better than classica at solving NP problems.
Re: The Transformer Network for the Traveling Salesman Problem
#18Earlier quoted context omitted.
> 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.
My 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 — wh…
Combinatorics (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.
Re: The Transformer Network for the Traveling Salesman Problem
#19For 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…
> 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.
> 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.
Re: The Transformer Network for the Traveling Salesman Problem
#20For 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…
Provably optimal? I thought TSP was NP-Hard and could only ever be solved via heuristics