# Forcing optimal solution for FindShortestTour

I use FindShortestTour as explained here and it works nicely for a small number of cities. However when I try this with as little as 16 cities, the given tour isn't optimal anymore. I've tried using different Methods but none of them gave me the optimal tour (solutions within a 5% to 400% range of the optimal solution).

How can I force Mathematica to give me the optimal solution?

Edit:

This is my code (pretty much copy-paste from the link above as I'm very new to Mathematica)

dim = 16;
max = 100;

(* create symmetric matrix with random integers *)
d = RandomInteger[max, {dim, dim}];
d = Table[If[i > j, d[[i, j]], d[[j, i]]], {i, 1, Length[d[]]}, {j, 1,Length[d[]]}];
(d[[#, #]] = Infinity) & /@ Range[dim];
d // Grid

(* find tour *)
{len, tour} = FindShortestTour[Range[dim], DistanceFunction -> (d[[#1, #2]] &),
Method -> "TwoOpt"]

(* display tour *)
GraphStyle -> "SmallNetwork", EdgeLabels -> "EdgeWeight"],
Style[UndirectedEdge[#1, #2], Thickness[.01], Red] & @@@ Partition[tour, 2, 1, 1]]

• "IntegerLinearProgramming" doesn't give you the shortest?
– Rojo
Oct 28, 2013 at 15:32
• @Rojo It's strangely enough one of the worst, it gave me 888 as distance whereas the optimal was 198. The best for this specific layout was TwoOpt giving me a solution of 205 but none of them ever seem to give me an optimal solution. (which I need to compare my algorithm against) Oct 28, 2013 at 15:35
• @Aerus Perhaps you should post you code?
– Lou
Oct 28, 2013 at 15:37
• The fact that "IntegerLinearProgramming" fails in such spectacular fashion seems to indicate the second problem today that has shown up in certain integer programming library code. I guess I need to file some reports. Oct 28, 2013 at 16:17
• Okay, this one at least will be fixed in a future release. Oct 28, 2013 at 17:23