Changeset 7558 for trunk/sources/HeuristicLab.Problems.TravelingSalesman/3.3/TravelingSalesmanProblem.cs

Timestamp:

03/06/12 01:43:06 (12 years ago)

Author:

abeham

Message:

#1782: trunk integration of problem instance development

• Adapted TSP and QAP to use the new feature
• Moved the TSPLIB importer dialog from the TSP plugin to the TSPLIB instances plugin (created a view for that provider)
• Created it as a default view for IHeuristicOptimizationProblem in order not to interfere with other problems do not yet work with this

File:

• trunk/sources/HeuristicLab.Problems.TravelingSalesman/3.3/TravelingSalesmanProblem.cs (modified) (5 diffs)

trunk/sources/HeuristicLab.Problems.TravelingSalesman/3.3/TravelingSalesmanProblem.cs

@@ -32 +32 @@
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 using HeuristicLab.PluginInfrastructure;
+using HeuristicLab.Problems.Instances;
 
 namespace HeuristicLab.Problems.TravelingSalesman {
@@ -37 +38 @@
   [Creatable("Problems")]
   [StorableClass]
-  public sealed class TravelingSalesmanProblem : SingleObjectiveHeuristicOptimizationProblem<ITSPEvaluator, IPermutationCreator>, IStorableContent {
+  public sealed class TravelingSalesmanProblem : SingleObjectiveHeuristicOptimizationProblem<ITSPEvaluator, IPermutationCreator>, IStorableContent,
+    IProblemInstanceConsumer<TSPData> {
+    private static readonly int DistanceMatrixSizeLimit = 1000;
     public string Filename { get; set; }
 
@@ -107 +110 @@
     public TravelingSalesmanProblem()
       : base(new TSPRoundedEuclideanPathEvaluator(), new RandomPermutationCreator()) {
-
       Parameters.Add(new ValueParameter<DoubleMatrix>("Coordinates", "The x- and y-Coordinates of the cities."));
       Parameters.Add(new OptionalValueParameter<DistanceMatrix>("DistanceMatrix", "The matrix which contains the distances between the cities."));
@@ -247 +249 @@
         evaluator.UseDistanceMatrixParameter.Hidden = true;
       }
+      if (Evaluator is ITSPDistanceMatrixEvaluator) {
+        var evaluator = (ITSPDistanceMatrixEvaluator)Evaluator;
+        evaluator.DistanceMatrixParameter.ActualName = DistanceMatrixParameter.Name;
+        evaluator.DistanceMatrixParameter.Hidden = true;
+      }
     }
     private void ParameterizeAnalyzers() {
@@ -310 +317 @@
 
     private void ClearDistanceMatrix() {
-      DistanceMatrixParameter.Value = null;
+      if (!(Evaluator is ITSPDistanceMatrixEvaluator))
+        DistanceMatrixParameter.Value = null;
     }
     #endregion
 
-    public void ImportFromTSPLIB(string tspFileName, string optimalTourFileName) {
-      TSPLIBParser tspParser = new TSPLIBParser(tspFileName);
-      tspParser.Parse();
-      Name = tspParser.Name + " TSP (imported from TSPLIB)";
-      if (!string.IsNullOrEmpty(tspParser.Comment)) Description = tspParser.Comment;
-      Coordinates = new DoubleMatrix(tspParser.Vertices);
-      if (tspParser.WeightType == TSPLIBParser.TSPLIBEdgeWeightType.EUC_2D) {
-        TSPRoundedEuclideanPathEvaluator evaluator = new TSPRoundedEuclideanPathEvaluator();
-        evaluator.QualityParameter.ActualName = "TSPTourLength";
-        Evaluator = evaluator;
-      } else if (tspParser.WeightType == TSPLIBParser.TSPLIBEdgeWeightType.GEO) {
-        TSPGeoPathEvaluator evaluator = new TSPGeoPathEvaluator();
-        evaluator.QualityParameter.ActualName = "TSPTourLength";
-        Evaluator = evaluator;
-      }
+    public void Load(TSPData data) {
+      if (data.Coordinates == null && data.Distances == null)
+        throw new System.IO.InvalidDataException("The given instance does not specify neither coordinates or distances!");
+      if (data.Dimension > DistanceMatrixSizeLimit && (data.DistanceMeasure == TSPDistanceMeasure.Att
+        || data.DistanceMeasure == TSPDistanceMeasure.Manhattan
+        || data.DistanceMeasure == TSPDistanceMeasure.Maximum
+        || data.DistanceMeasure == TSPDistanceMeasure.UpperEuclidean))
+        throw new System.IO.InvalidDataException("The given instance uses an unsupported distance measure and is too large for using a distance matrix.");
+      if (data.Coordinates != null && data.Coordinates.GetLength(1) != 2)
+        throw new System.IO.InvalidDataException("The coordinates of the given instance are not in the right format, there need to be one row for each customer and two columns for the x and y coordinates.");
+
+      Name = data.Name;
+      Description = data.Description;
+
+      if (data.Coordinates != null && data.Coordinates.GetLength(0) > 0)
+        Coordinates = new DoubleMatrix(data.Coordinates);
+
+      TSPEvaluator evaluator;
+      if (data.DistanceMeasure == TSPDistanceMeasure.Att
+        || data.DistanceMeasure == TSPDistanceMeasure.Manhattan
+        || data.DistanceMeasure == TSPDistanceMeasure.Maximum
+        || data.DistanceMeasure == TSPDistanceMeasure.UpperEuclidean) {
+        evaluator = new TSPDistanceMatrixEvaluator();
+        UseDistanceMatrix = new BoolValue(true);
+        DistanceMatrix = new DistanceMatrix(data.GetDistanceMatrix());
+      } else if (data.DistanceMeasure == TSPDistanceMeasure.Direct && data.Distances != null) {
+        evaluator = new TSPDistanceMatrixEvaluator();
+        UseDistanceMatrix = new BoolValue(true);
+        DistanceMatrix = new DistanceMatrix(data.Distances);
+      } else {
+        DistanceMatrix = null;
+        UseDistanceMatrix = new BoolValue(data.Dimension <= DistanceMatrixSizeLimit);
+        switch (data.DistanceMeasure) {
+          case TSPDistanceMeasure.Euclidean:
+            evaluator = new TSPEuclideanPathEvaluator();
+            break;
+          case TSPDistanceMeasure.RoundedEuclidean:
+            evaluator = new TSPRoundedEuclideanPathEvaluator();
+            break;
+          case TSPDistanceMeasure.Geo:
+            evaluator = new TSPGeoPathEvaluator();
+            break;
+          default:
+            throw new InvalidDataException("An unknown distance measure is given in the instance!");
+        }
+      }
+      evaluator.QualityParameter.ActualName = "TSPTourLength";
+      Evaluator = evaluator;
+
+      BestKnownSolution = null;
       BestKnownQuality = null;
-      BestKnownSolution = null;
-
-      if (!string.IsNullOrEmpty(optimalTourFileName)) {
-        TSPLIBTourParser tourParser = new TSPLIBTourParser(optimalTourFileName);
-        tourParser.Parse();
-        if (tourParser.Tour.Length != Coordinates.Rows) throw new InvalidDataException("Length of optimal tour is not equal to number of cities.");
-        BestKnownSolution = new Permutation(PermutationTypes.RelativeUndirected, tourParser.Tour);
+
+      if (data.BestKnownTour != null) {
+        try {
+          EvaluateAndLoadTour(data.BestKnownTour);
+        } catch (InvalidOperationException) {
+          if (data.BestKnownQuality.HasValue)
+            BestKnownQuality = new DoubleValue(data.BestKnownQuality.Value);
+        }
+      } else if (data.BestKnownQuality.HasValue) {
+        BestKnownQuality = new DoubleValue(data.BestKnownQuality.Value);
       }
       OnReset();
     }
-    public void ImportFromTSPLIB(string tspFileName, string optimalTourFileName, double bestKnownQuality) {
-      ImportFromTSPLIB(tspFileName, optimalTourFileName);
-      BestKnownQuality = new DoubleValue(bestKnownQuality);
+
+    public void EvaluateAndLoadTour(int[] tour) {
+      var route = new Permutation(PermutationTypes.RelativeUndirected, tour);
+      BestKnownSolution = route;
+
+      double quality;
+      if (Evaluator is TSPDistanceMatrixEvaluator) {
+        quality = TSPDistanceMatrixEvaluator.Apply(DistanceMatrix, route);
+      } else if (Evaluator is TSPCoordinatesPathEvaluator) {
+        quality = TSPCoordinatesPathEvaluator.Apply((TSPCoordinatesPathEvaluator)Evaluator, Coordinates, route);
+      } else {
+        throw new InvalidOperationException("Cannot calculate solution quality, evaluator type is unknown.");
+      }
+      BestKnownQuality = new DoubleValue(quality);
     }
   }