1
$\begingroup$

I am doing Week_4 of https://www.coursera.org/learn/discrete-optimization/
stuck in solving TSP.
As there are a lot of methods to solve this problem, I am currently coding
Guided Local Search as described here. This basically penalizes the longest edge and repeatedly searches that neighborhood until no improvement found. To search the neighborhood faster, it uses Fast Local search which basically marks a vertex inactive if no improving (2-Opt) moves are found.

My problem is that I do not see any improvement after the first Fast Local Search(FLS).
Any insights on this?

Also, what is the suggested method to solve TSP in order to ease?
Like I know these are methods
- Simulated Annealing with re-heat.
- Mixed Integer Programming(MIP) with Gomory Cut.
- LK(Lein-Kerninghan), LKH, ILKH heuristics
- GLS+FLS (I find this easy to start with)
- Hybrid approaches like MIP + SA.

|cite|improve this question
$\endgroup$
  • $\begingroup$ This is a rather broad question. People have written surveys on practical approaches to TSP. Perhaps you could take a look at some of them. $\endgroup$ – Yuval Filmus Feb 15 at 5:28
  • $\begingroup$ Thanks, should I try 3-opt, when 2 opt stuck in local minima $\endgroup$ – Chits Feb 15 at 5:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.