7

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?

maxmitz
  • 659
  • 3
  • 11
  • Constraint programming is not an exact method. – Kuifje Sep 20 '21 at 18:20
  • 2
    @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. – prubin Sep 20 '21 at 18:37
  • Also, checkout ortools' options for a non exhaustive list of other options (in the heuristic world). – Kuifje Sep 20 '21 at 18:37
  • @prubin thanks for the clarification. In practice, can we say that constraint programming is less effective to find optimal solutions compared to IP ? I was told this, and the fact that ortools combines CP + localsearch kind of points in that direction, but I would be happy to learn that it is not the case! – Kuifje Sep 20 '21 at 18:39
  • @Kuifje I abandoned the quest for valid generalizations about CP v. IP a while back. My suspicion (and I stress the word "suspicion") is that, on discrete optimization problems in general, CP tends to have weaker bounds than IP but perhaps processes nodes in the search tree faster than IP (meaning propagation of integer constraints is maybe faster than dual simplex pivots, cut generation etc.). As best I know, CP tends to be faster than IP solving (to optimality) at least some kinds of machine scheduling problems. – prubin Sep 20 '21 at 18:43
  • 2
    @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 :). – Joris Kinable Sep 20 '21 at 19:00
  • @JorisKinable Thank you for the clarification ! – Kuifje Sep 20 '21 at 19:02
  • 1
    @JorisKinable As soon as someone asked that question, some moderator would close it for being opinion-based. :-( – prubin Sep 20 '21 at 19:02
  • @prubin If I thought the question was reasonably well-written, I'd vote to reopen, once I became aware of the closure. – Mark L. Stone Sep 20 '21 at 19:21
  • @MarkL.Stone As would I, but we likely would be in the minority. Maybe someone could try a "community wiki" page, listing problems better handled by one approach or the other. Even then, it might be too opinion-based. Someone might say "I tried both IP and CP on problem X, and CP won", but then what about a stronger IP formulation, or Benders / Branch-and-Price / other advance IP approach? On the flip side, if IP won, which CP solver did you use, because my impression is that the global constraints supported vary widely from solver to solver. – prubin Sep 20 '21 at 19:30
  • @prubin And all of those points would be excellent for discussion in the answers. – Mark L. Stone Sep 20 '21 at 19:39
  • OR-community-discord-server: https://discord.gg/k5AtFccjne join us to get a bigger live-community. – Eddiee Sep 20 '21 at 21:26

2 Answers2

13

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.

prubin
  • 39,078
  • 3
  • 37
  • 104
8

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.
Joris Kinable
  • 3,451
  • 8
  • 19