Enable to solve TSPs which are specified only by a distance matrix

[HeuristicLab-Trac-Bot]

Issue migrated from trac ticket # 1396

milestone: HeuristicLab 3.3.7 | component: Problems.TravelingSalesman | priority: highest | resolution: done

2011-01-26 22:04:14: @s-wagner created the issue

---

It should be possible to specify a TSP only by its distance matrix and not by its city coordinates. Although this is already possible, it is not very comfortable and intuitive, as the city coordinates are always required. Furthermore, the TSPLIB importer should be enhanced to enable imports of TSPLIB files which only contain a distance matrix.

[HeuristicLab-Trac-Bot]

2011-02-05 02:27:14: @s-wagner commented

---

Follow-up from ticket #1333: The distance matrix should not be calculated in the evaluators but in the problem itself (for example during the import or by a specific user action).

[HeuristicLab-Trac-Bot]

2012-03-06 14:36:11: @abeham changed milestone from HeuristicLab 3.3.x Backlog to HeuristicLab 3.3.7

[HeuristicLab-Trac-Bot]

2012-03-06 14:36:11: @abeham changed owner from swagner to abeham

[HeuristicLab-Trac-Bot]

2012-03-06 14:36:11: @abeham changed status from new to accepted

[HeuristicLab-Trac-Bot]

2012-03-06 14:38:26: @abeham commented

---

part of #1782 was to update the TSPLIB parser. It can now parse any file in TSPLIB format, including those that are only specified by a distance matrix. Also a TSPDistanceMatrixEvaluator was created when integrating this into the trunk. When this evaluator is selected, the distance matrix will not be cleared when the coordinates change.

[HeuristicLab-Trac-Bot]

2012-03-15 14:30:03: @abeham commented

---

r7621:

• Fixed loading of instances that did not specify coordinates (visual or actual ones)
• Turned coordinates into an OptionalValueParameter
• Added checks in relevant operators that throw an exception if they can neither find coordinates or distances
• Writing a message to the visualization if coordinates are not defined

[HeuristicLab-Trac-Bot]

2012-06-05 13:07:56: @abeham changed owner from abeham to swagner

[HeuristicLab-Trac-Bot]

2012-06-05 13:07:56: @abeham changed status from accepted to reviewing

[HeuristicLab-Trac-Bot]

2012-07-03 15:11:05: @mkommend changed owner from swagner to mkommend

[HeuristicLab-Trac-Bot]

2012-07-03 16:18:43: @mkommend commented

---

Reviewed r7621 and tested the optimization of TSP problems with no given coordinates and everything works as expected, except changing of the evaluator (also with the DistanceMatrixEvaluator) which leads to an exception. I think there is a wiring mistake in the TSPProblem.

[HeuristicLab-Trac-Bot]

2012-07-03 16:18:43: @mkommend changed owner from mkommend to abeham

[HeuristicLab-Trac-Bot]

2012-07-03 16:52:28: @mkommend changed status from reviewing to assigned

[HeuristicLab-Trac-Bot]

2012-07-03 22:44:34: @abeham commented

---

Actually it's a configuration mistake: The problematic case is when you switch to the TSPDistanceMatrixEvaluator, but there's no DistanceMatrix defined or when you want a coordinate based evaluator, but there are no Coordinates defined. I would want to throw an exception in this case, but cannot as this not caught anywhere and would crash the optimizer. Here's the responsible code:

private void ParameterizeSolutionCreator() {
      if (Evaluator is ITSPDistanceMatrixEvaluator && DistanceMatrix != null)
        SolutionCreator.LengthParameter.Value = new IntValue(DistanceMatrix.Rows);
      else if (Evaluator is ITSPCoordinatesPathEvaluator && Coordinates != null)
        SolutionCreator.LengthParameter.Value = new IntValue(Coordinates.Rows);
      else SolutionCreator.LengthParameter.Value = null;
      SolutionCreator.LengthParameter.Hidden = SolutionCreator.LengthParameter.Value != null;
      SolutionCreator.PermutationTypeParameter.Value = new PermutationType(PermutationTypes.RelativeUndirected);
      SolutionCreator.PermutationTypeParameter.Hidden = true;
    }

In r8208 I added code to show only error dialog when the evaluator is currently not supported so that the user is immediately informed. This in turn required an explicit dependency to System.Windows.Forms. It should be a rare case as the users normally don't have to touch the evaluators a lot. Do you think this is enough to handle this issue?

[HeuristicLab-Trac-Bot]

2012-07-03 22:44:34: @abeham changed owner from abeham to mkommend

[HeuristicLab-Trac-Bot]

2012-07-03 22:44:34: @abeham changed status from assigned to reviewing

[HeuristicLab-Trac-Bot]

2012-07-04 13:15:59: @mkommend commented

---

Reviewed r8208 and the source looks ok, but loading different problem instances does not work correctly (e.g., gil262 => fri26).

[HeuristicLab-Trac-Bot]

2012-07-04 13:15:59: @mkommend changed owner from mkommend to abeham

[HeuristicLab-Trac-Bot]

2012-07-04 13:15:59: @mkommend changed status from reviewing to assigned

[HeuristicLab-Trac-Bot]

2012-07-04 23:54:51: @abeham commented

---

r8221: fixed loading errors when switching from coordinates to distance matrix evaluation

Thanks for the test case. I think it should work correctly now.

[HeuristicLab-Trac-Bot]

2012-07-04 23:54:51: @abeham changed owner from abeham to mkommend

[HeuristicLab-Trac-Bot]

2012-07-04 23:54:51: @abeham changed status from assigned to reviewing

[HeuristicLab-Trac-Bot]

2012-07-05 09:19:51: @mkommend changed owner from mkommend to abeham

[HeuristicLab-Trac-Bot]

2012-07-05 09:19:51: @mkommend changed status from reviewing to readytorelease

[HeuristicLab-Trac-Bot]

2012-07-08 04:30:05: @gkronber removed resolution

[HeuristicLab-Trac-Bot]

2012-07-08 04:30:05: @gkronber changed status from readytorelease to closed