# I can't understand FindShortest Tour

I can't understand the function FindShortestTour because of the result:

FindShortestTour[{ {0, 1}, {5, 1}, {2, 1}, {10, 1}}]

{20, {1, 2, 4, 3}}


and I think that the result should be:

 {10, {1, 3, 2, 4}}


or

 {10, {4, 2, 3, 1}}

-
A tour goes back to the starting point. Your proposed tours, if they do so as well, have length 20 and thus are no shorter than the one found by FoundShortestTour. That is, the distance is calculated as Total[Norm /@ (pts[[tour]] - pts[[RotateLeft[tour]]])] (or something equivalent to that), where pts is the list of points and tour is the result given by FindShortestTour. Another way to see this is to specify Method -> "AllTours" or Method -> "IntegerLinearProgramming", both of which find guaranteed optimal tours. The result won't change. –  Oleksandr R. Jun 23 '13 at 0:22
@OleksandrR. should write this as an answer since it directly addresses the OPs question of what it means to be a "shortest tour". –  bill s Jun 23 '13 at 5:04
@bill-s I understand Oleksandr R. A tour must come back (in the last "movement") to the starting point. In the first solution, The tour is START Visiting 1, Visit2, Visit,4,visit 3, and come back to Visit 1. FINISH. –  Mika Ike Jun 23 '13 at 8:58

A tour must return to the starting point; i.e. it is a cycle. Your proposed tours with lengths of 10 are not, and therefore could not have been found by FindShortestTour. Calculating the length explicitly shows that all three (the tour found by FindShortestTour and your proposed tours, when interpreted as returning to the beginning) have a length of 20, which is the minimum possible in this example:

pts = {{0, 1}, {5, 1}, {2, 1}, {10, 1}};
{len, tour} = FindShortestTour[pts];

ClearAll[tourEdgeLengths, tourLength];
tourEdgeLengths[pts_, tour_] := Norm /@ (pts[[tour]] - pts[[RotateLeft[tour]]]);
tourLength[pts_, tour_] := Total@tourEdgeLengths[pts, tour];

tourLength[pts, tour] (* FindShortestTour result is {1, 2, 4, 3} *)
(* -> 20 *)

tourLength[pts, {1, 3, 2, 4}]
(* -> 20 *)

tourLength[pts, {4, 2, 3, 1}]
(* -> 20 *)


Indeed, the methods "AllTours" and "IntegerLinearProgramming" are guaranteed to find the shortest tour, and these produce the same result as the default method.

The result obtained from FindShortestTour is a good example of the fact that, when seeking a traversal that is not a tour, in general one can not simply find the shortest cycle and then delete its longest edge to get the optimum solution. This would be the case for your tour {1, 3, 2, 4}:

tourEdgeLengths[pts, {1, 3, 2, 4}]
(* -> {2, 3, 5, 10} *)


i.e., deleting the last edge (4$\rightarrow$1, length 10) produces the shortest Hamiltonian path. But, when considering the equally good tour {1, 2, 4, 3},

tourEdgeLengths[pts, {1, 2, 4, 3}]
(* -> {5, 5, 8, 2} *)


we see that deleting the edge 4$\rightarrow$3 (length 8) leaves us with a non-optimal, length-12 traversal.

-

I can confirm that result (Linux, 64 bit). Indeed, a good example that shows how bad some (most) outputs of FindShortestTour are. I've made a few posts regarding the add-on package JVMTools already, for example here, so I'll just keep it with that link. JVMTools uses industrial-strength algorithms that produce optimal solutions for a few hundred nodes in a few seconds, and solutions that are only 1 - 2% above optimal for a few thousand nodes. All algorithms use concurrency to submit competing strategies and initial nodes (and then returns either all solutions or only the best, based on the user's choice), and also uses ant-colony / multi-agent optimization algorithms for outstanding quality and speed results.

Disclosure: I am the owner of Lauschke Consulting, which is the business that sells JVMTools commercially.

-
Can you please edit the second sentence where you claim that this is a good example of bad FindShortestTour input? –  Jacob Akkerboom Jun 23 '13 at 9:57
@Jacob: I think there is no need to edit, my sentence is correct. It is a good example that shows how bad FindShortestTour outputs can be. I never made a claim about FindShortestTour inputs (as that comes from the user). –  Andreas Lauschke Jun 23 '13 at 10:12
Ah yes, I should have said output. But please see the comment and answer by OleksandrR and consider the difference between finding a minimum length tour (Hamiltonian cycle) and a minimum length Hamiltonian path. –  Jacob Akkerboom Jun 23 '13 at 10:17
To be fair, I have asked a question on the meta site featuring this answer as a major example. –  Jacob Akkerboom Jul 12 '13 at 1:41

FindShortestTour is a complex function with multiple operation levels.

First of all there are two steps for FindShortestTour:

1. Tour generation
2. Tour improvement

FindShortestTour implements several tour generation methods. Space-filling curves is one for instance, another one is CCA (convex hull, cheapest insertion, angle selection).

All the methods for tour generation and tour improvement are not applied to your example, since there are not enough points. In your case FindShortestPath is clever enough and will switch to Minimize, implementing an elaborate Integer Linear Programming approach. (Caution! That _Mathematica) is using [N]Minimize internally might not be true at all. Let's suppose it does.)

Let's try to mimic what Mathematica is doing under the hood, when switching to Minimize.

• set up a variable which holds 1 or 0 if an edge from one point $i$ to another point $j$ is in the optimal tour
• minimize the total cost of the tour defined by the 1s

The problem with this approach is that the solution will be a collection of cycles.

Here the tour improvement step comes into play.

The first cycles after the first call to Minimize are killed. This is repeated as long as there is a cycle which involves all n points. Perfectly if this last cycle is a Hamilton cycle and the optimal tour (please see OleksandrR's answer).

The whole iterative process seems to be rather costly and it is indeed. That's why FindShortestTour switches to it only if the amount of points is smaller than a threshold.

Surprisingly it terminates quickly if the threshold is low enough.

The solution to your problem is {1, 3, 2, 4} and {1, 2, 4, 3} as well. They're all straight lines and since Euclid we know that lines are the shortest connections :). And as OleksandR already pointed out, that a tour is only a tour if you return to the starting point that's why the length is 20.

-
Does FindShortestTour really call Minimize (internally)? I did not find this in the docs, nor in Information[FindShortestTour] after removing the attribute ReadProtected, nor in Trace[FindShortestTour[{{0, 1}, {5, 1}, {2, 1}, {10, 1}}], TraceInternal -> True]. I do not think there will be a tour improvement step after the linear programming, as I think the linear programming will yield an optimal solution directly. There are probably relaxed linear programs which return some cycles, but there also equivalent formulations of TSP using LP. I suppose Mathematica just uses that. –  Jacob Akkerboom Jun 23 '13 at 11:34
@JacobAkkerboom hmmm. maybe that shot was careless. I suppose yes, if Mma switches to an ILP approach...and what function is better suited for that than [N]Minimize. Well I guess your are right concerning those points that there will be no improvement step, but if there are more points I suppose there will be tour improvement involved, if they are using Minimize for that. The algorithm I described is based on iteratively minimizing the result until you get your hamilton and tsp. –  Stefan Jun 23 '13 at 11:41