# 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[[1]]]}, {j, 1,Length[d[[1]]]}];
(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 '13 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) –  Aerus Oct 28 '13 at 15:35
@Aerus Perhaps you should post you code? –  Lou Oct 28 '13 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. –  Daniel Lichtblau Oct 28 '13 at 16:17
Okay, this one at least will be fixed in a future release. –  Daniel Lichtblau Oct 28 '13 at 17:23