4
$\begingroup$

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]]
Improve this question
$\endgroup$
9
  • $\begingroup$ "IntegerLinearProgramming" doesn't give you the shortest? $\endgroup$
    – Rojo
    Oct 28, 2013 at 15:32
  • $\begingroup$ @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) $\endgroup$
    – Aerus
    Oct 28, 2013 at 15:35
  • $\begingroup$ @Aerus Perhaps you should post you code? $\endgroup$
    – Lou
    Oct 28, 2013 at 15:37
  • 3
    $\begingroup$ 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. $\endgroup$
    – Daniel Lichtblau
    Oct 28, 2013 at 16:17
  • 3
    $\begingroup$ Okay, this one at least will be fixed in a future release. $\endgroup$
    – Daniel Lichtblau
    Oct 28, 2013 at 17:23

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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