Opened 7 years ago

Closed 5 years ago

#1396 closed enhancement (done)

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

Reported by: swagner Owned by: abeham
Priority: highest Milestone: HeuristicLab 3.3.7
Component: Problems.TravelingSalesman Version: 3.3.7
Keywords: Cc:

Description

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.

Change History (13)

comment:1 Changed 7 years ago by swagner

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).

comment:2 Changed 6 years ago by abeham

  • Milestone changed from HeuristicLab 3.3.x Backlog to HeuristicLab 3.3.7
  • Owner changed from swagner to abeham
  • Status changed from new to accepted

comment:3 Changed 6 years ago by abeham

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.

comment:4 Changed 6 years ago by abeham

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

comment:5 Changed 5 years ago by abeham

  • Owner changed from abeham to swagner
  • Status changed from accepted to reviewing

comment:6 Changed 5 years ago by mkommend

  • Owner changed from swagner to mkommend

comment:7 Changed 5 years ago by mkommend

  • Owner changed from mkommend to abeham

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.

comment:8 Changed 5 years ago by mkommend

  • Status changed from reviewing to assigned

comment:9 Changed 5 years ago by abeham

  • Owner changed from abeham to mkommend
  • Status changed from assigned to reviewing

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?

comment:10 Changed 5 years ago by mkommend

  • Owner changed from mkommend to abeham
  • Status changed from reviewing to assigned

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

comment:11 Changed 5 years ago by abeham

  • Owner changed from abeham to mkommend
  • Status changed from assigned to reviewing

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

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

comment:12 Changed 5 years ago by mkommend

  • Owner changed from mkommend to abeham
  • Status changed from reviewing to readytorelease

comment:13 Changed 5 years ago by gkronber

  • Resolution set to done
  • Status changed from readytorelease to closed
  • Version changed from 3.3.2 to 3.3.7
Note: See TracTickets for help on using tickets.