7
$\begingroup$

Exists a list of categories that include possibilities to solve a travelling salesman problem (TSP)? I know, for example:

  • Exact methods
    • Integer Linear Programming
    • Dynamic Programming
    • Constraint Programming
  • Heuristics
    • Construction heuristics
      • Nearest Neighbour
    • Improvement heuristics
      • k-opt
    • Metaheuristics
      • Ant-Colony-Optimisation

Is there a complete list of all these possibilities? Into which categories can they be ordered?

Improve this question
$\endgroup$
12
  • $\begingroup$ Constraint programming is not an exact method. $\endgroup$
    – Kuifje
    Sep 20, 2021 at 18:20
  • 2
    $\begingroup$ @Kuifje Constraint programming would be exact in the same sense that IP is ... if you let the solver run until the search tree has been exhausted, you have a definitive answer. $\endgroup$
    – prubin ♦
    Sep 20, 2021 at 18:37
  • $\begingroup$ Also, checkout ortools' options for a non exhaustive list of other options (in the heuristic world). $\endgroup$
    – Kuifje
    Sep 20, 2021 at 18:37
  • 2
    $\begingroup$ @kuifje On the contrary, CP is an exact method. Similar to IP, CP performs a tree search. For both constraint optimization problems and constraint satisfiability problems, CP provides provable, optimal solutions. The techniques employed by CP/IP are very different, and as such, there are many CP problems that are horrible to solve with IP, and vice versa. For a long time, CP struggled with optimization problems since it could not infer bounds. Recently, CP solvers have been attempting to generate bounds as well. CP vs IP would make a good or.se question :). $\endgroup$
    – Joris Kinable
    Sep 20, 2021 at 19:00
  • 1
    $\begingroup$ @JorisKinable As soon as someone asked that question, some moderator would close it for being opinion-based. :-( $\endgroup$
    – prubin ♦
    Sep 20, 2021 at 19:02

2 Answers 2

Reset to default
13
$\begingroup$

I doubt there is a complete listing of every possible approach to TSPs. You can find a significant amount of information on Bill Cook's site. Bill Cook wrote what I believe many consider the definitive book about TSPs ("In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation", Princeton University Press, 2012) and is one of the developers of the Concorde TSP solver. Cook's TSP web site contains examples, teaching tools, test data, and links to some rather large solved instances.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ I would suggest including at least some relevant information from that site in this answer. The answer would not be helpful to anyone who is unable to visit the site due to e.g. internet restrictions, or in case the link dies, not to mention that it just adds a layer of indirection. Related: Are answers that just contain links elsewhere really "good answers"? $\endgroup$
    – NotThatGuy
    Sep 21, 2021 at 11:35
  • $\begingroup$ @NotThatGuy I added something about the content of the first site I linked, along with some info about Prof. Cook. $\endgroup$
    – prubin ♦
    Sep 21, 2021 at 15:29
8
$\begingroup$

Some additional sources to help you answer your question:

  • Cook, W. "In pursuit of the traveling salesman: mathematics at the limits of computation. 2012."
  • Gutin, Gregory, and Abraham P. Punnen, eds. The traveling salesman problem and its variations. Vol. 12. Springer Science & Business Media, 2006.
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.