Using Julia+JuMP to Solve a TSP with Lazy Constraints

http://iaindunning.com/2013/mip-callback.html

by idunning • 13 years ago

52 6 13 years ago

elchief• 13 years ago

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.

StefanKarpinski2• 13 years ago

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.

hartror• 13 years ago

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

idunning2• 13 years ago

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

idunning2• 13 years ago

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.

Using Julia+JuMP to Solve a TSP with Lazy Constraints

Related Stories