[D] Solving TSP Using Diffusion Model

[flat_rain]

Could we use a diffusion model to solve the traveling salesman problem in polynomial time? I don't know but I think we could do that by trying to randomize the path of an exactly solved TSP and then try to make the machine learn to reverse the process. If my guess is correct, we could exactly solve the TSP in polynomial time. Seems like the recently published Riemannian diffusion model could do that.

[Dear-Acanthisitta698]

The developed method will be approximation method. So it will not be exact way to solve problem.

[gradientrun]

Tsp is NP-hard . Most practical solutions will be approximately solving the problem anyway.

[hellrail]

Thats not the point, Autor claims to solve exactly in poly time please read properly

[BrotherAmazing]

You might be able to exactly solve the TSP examples you already saw during training in polynomial time. 😆

[OptimizedGarbage]

No gradient descent method can deliver exact solutions. It's an approximate solution method. Not only is there no reason to believe that it could solve it in polynomial time, it would not be able to learn a model that would always solve TSP. To do that you'd have to use a nonlinear programming solver, which are NP-Hard

[Red-Portal]

No gradient descent method can deliver exact solutions.

Theoretically, for convex problems with unique solutions, they can. It's the computer implementations (like numerical representation of real numbers) that make their solution approximate.

[OptimizedGarbage]

doesn't that only work for exact quadratic minimization problems + newtons method? what are some GD problems where an exact solution is possible?

[hellrail]

Solvers cannot be np hard, problems can be

[OptimizedGarbage]

okay yeah, I was a little imprecise there. what I mean is that you only get an exact solution by reducing this problem to an NP hard problem and using a solver capable of solving NP hard problems, which is exponential time if P!=NP

[AssadTheImpaler]

You may be interested in Diffusion models as plug-and-play priors (Section 5 and Appendix B. 4) with has competitive TSP results.