# 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 *)

• @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) – Aerus Oct 28 '13 at 15:35