Return to Revisions

This gives the same (optimal) answer as Daniel Lichtblau's answer for the given example. Integer linear programming is also used, but in this answer this is done by FindShortestTour.

max = 20;
nn = 20;
SeedRandom[1]
pts = RandomInteger[max, {nn, 2}]
boolPts =
  Join[
   Transpose@Join[{-Range[nn]}, Transpose@ pts], 
   Table[{i, 0, 0}, {i,  nn}]];

bound = 2 max^2;
tour = FindShortestTour[boolPts, 
   DistanceFunction -> (If[#[[1]] +  #2[[1]] == 0, -bound, 
       EuclideanDistance[#[[2 ;;]], #2[[2 ;;]]]] &), 
   Method -> "IntegerLinearProgramming"];