Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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 *)
HighlightGraph[ WeightedAdjacencyGraph[d, DirectedEdges -> False, 
  GraphStyle -> "SmallNetwork", EdgeLabels -> "EdgeWeight"], 
 Style[UndirectedEdge[#1, #2], Thickness[.01], Red] & @@@ Partition[tour, 2, 1, 1]]
share|improve this question
    
"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
2  
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
2  
Okay, this one at least will be fixed in a future release. –  Daniel Lichtblau Oct 28 '13 at 17:23
show 2 more comments

1 Answer 1

Daniel Lichtblau has confirmed that this is a problem with the integer linear programming code. Moreover, a bug report has been filed and the problem will be addressed in a future version.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.