Return to Answer

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,
       If[
        #[[1]] #2[[1]] < 0 
        ,
        bound
        ,
        EuclideanDistance[#[[2 ;;]], #2[[2 ;;]]]
        ]] &), Method -> "IntegerLinearProgramming"];

resultLength = nn*bound + N@First@tour

30.8036

pairs = pts[[#]] & /@ Partition[tour[[2]], 2][[1 ;; -1 ;; 2]]
resultLength == Total[EuclideanDistance @@@ pairs]

{{{5, 0}, {7, 0}}, {{5, 12}, {3, 10}}, {{0, 0}, {2, 3}}, {{11, 
   2}, {12, 0}}, {{19, 4}, {20, 3}}, {{17, 11}, {19, 8}}, {{15, 
   6}, {19, 5}}, {{16, 14}, {18, 16}}, {{7, 3}, {4, 2}}, {{3, 8}, {0, 
   4}}}
 True

This gives the same (optimal) result 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,
       If[
        #[[1]] #2[[1]] < 0 
        ,
        bound
        ,
        EuclideanDistance[#[[2 ;;]], #2[[2 ;;]]]
        ]] &), Method -> "IntegerLinearProgramming"];

resultLength = nn*bound + N@First@tour

30.8036

pairs = pts[[#]] & /@ Partition[tour[[2]], 2][[1 ;; -1 ;; 2]]
resultLength == Total[EuclideanDistance @@@ pairs]

{{{5, 0}, {7, 0}}, {{5, 12}, {3, 10}}, {{0, 0}, {2, 3}}, {{11, 
   2}, {12, 0}}, {{19, 4}, {20, 3}}, {{17, 11}, {19, 8}}, {{15, 
   6}, {19, 5}}, {{16, 14}, {18, 16}}, {{7, 3}, {4, 2}}, {{3, 8}, {0, 
   4}}}
 True

Hmm there may be something wrong, let's see

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"];

resultLength = nn*bound + N@First@tour

30.8036

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,
       If[
        #[[1]] #2[[1]] < 0 
        ,
        bound
        ,
        EuclideanDistance[#[[2 ;;]], #2[[2 ;;]]]
        ]] &), Method -> "IntegerLinearProgramming"];

resultLength = nn*bound + N@First@tour

30.8036

pairs = pts[[#]] & /@ Partition[tour[[2]], 2][[1 ;; -1 ;; 2]]
resultLength == Total[EuclideanDistance @@@ pairs]

{{{5, 0}, {7, 0}}, {{5, 12}, {3, 10}}, {{0, 0}, {2, 3}}, {{11, 
   2}, {12, 0}}, {{19, 4}, {20, 3}}, {{17, 11}, {19, 8}}, {{15, 
   6}, {19, 5}}, {{16, 14}, {18, 16}}, {{7, 3}, {4, 2}}, {{3, 8}, {0, 
   4}}}
 True

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"];

Hmm there may be something wrong, let's see

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"];

resultLength = nn*bound + N@First@tour

30.8036