Using Julia+JuMP to Solve a TSP with Lazy Constraints

iaindunning.com

52 points·idunning··6 comments

This is very cool. Any notion of how the performance compares to real TSP solvers? Presumably they pull all sorts of dirty tricks to be as fast as possible.

It also strikes me that this is going to be great for comparing the performance of various solvers without having to rewrite all the code every time since you can use the same code across all backends.

My understanding from my optimisation research co-workers is a MIP isn't ideal for TSP and there are better ways, such as meta-heuristics.

http://en.wikipedia.org/wiki/Metaheuristic

They can be OK if being optimal isn't a concern, or the problem isn't too hard.

Not sure exactly, but I guess the dirty tricks are what really makes the difference. If you want to optimally solve a TSP, and know you are optimal when you stop, this is the approach you would use in practice - as far as I know it is the only thing that scales well. Its the underlying principle behind Concorde (http://www.math.uwaterloo.ca/tsp/concorde.html) which AFAIK is the best TSP solver out there.

SAS might have an issue with the name JuMP when then have a product named JMP, pronounced "jump".

I don't think their trademark covers names that are standard words merely similar to theirs, but it might be a point of confusion.

Reply on news.ycombinator.com