Changeset 13412 for branches/PTSP/HeuristicLab.Problems.Instances.TSPLIB/3.3

Timestamp:

11/28/15 23:38:51 (9 years ago)

Author:

abeham

Message:

#2221:

• Completely refactored PTSP branch
  • Added two sets of problem instances based on TSPLIB: homogeneous and heterogeneous
  • Implemented missing EvaluateByCoordinates for 1-shift moves
  • Made it clear that move evaluators are for estimated PTSP only
  • Changed parameter realization from a rather strange list of list of ints to a list of bool arrays
  • Reusing code of the 2-opt and 1-shift move evaluators in 2.5 move evaluator
  • Introducing distance calculators to properly handle the case when no distance matrix is given (previous code only worked with distance matrix and without only with euclidean distance in some settings)
  • Fixed several smaller code issues: protected, static, method parameters, copy & paste, interfaces, naming, parameters, serialization hooks, license headers, doc comments, data types

Location:

branches/PTSP/HeuristicLab.Problems.Instances.TSPLIB

Files:

• . (copied) (copied from trunk/sources/HeuristicLab.Problems.Instances.TSPLIB)
• 3.3/HeuristicLab.Problems.Instances.TSPLIB-3.3.csproj (modified) (9 diffs)
• 3.3/MarsagliaRandom.cs (added)
• 3.3/TSPLIBATSPInstanceProvider.cs (modified) (1 diff)
• 3.3/TSPLIBCVRPInstanceProvider.cs (modified) (1 diff)
• 3.3/TSPLIBHeterogeneousPTSPDataDescriptor.cs (copied) (copied from trunk/sources/HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBDataDescriptor.cs) (1 diff)
• 3.3/TSPLIBHeterogeneousPTSPInstanceProvider.cs (copied) (copied from trunk/sources/HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBTSPInstanceProvider.cs) (3 diffs)
• 3.3/TSPLIBHomogeneousPTSPDataDescriptor.cs (copied) (copied from trunk/sources/HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBDataDescriptor.cs) (1 diff)
• 3.3/TSPLIBHomogeneousPTSPInstanceProvider.cs (copied) (copied from trunk/sources/HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBTSPInstanceProvider.cs) (3 diffs)
• 3.3/TSPLIBInstanceProvider.cs (modified) (2 diffs)
• 3.3/TSPLIBTSPInstanceProvider.cs (modified) (1 diff)

branches/PTSP/HeuristicLab.Problems.Instances.TSPLIB/3.3/HeuristicLab.Problems.Instances.TSPLIB-3.3.csproj

@@ -19 +19 @@
     <DebugType>full</DebugType>
     <Optimize>false</Optimize>
-    <OutputPath>..\..\bin\</OutputPath>
+    <OutputPath>..\..\..\..\trunk\sources\bin\</OutputPath>
     <DefineConstants>DEBUG;TRACE</DefineConstants>
     <ErrorReport>prompt</ErrorReport>
@@ -28 +28 @@
     <DebugType>pdbonly</DebugType>
     <Optimize>true</Optimize>
-    <OutputPath>..\..\bin\</OutputPath>
+    <OutputPath>..\..\..\..\trunk\sources\bin\</OutputPath>
     <DefineConstants>TRACE</DefineConstants>
     <ErrorReport>prompt</ErrorReport>
@@ -42 +42 @@
   <PropertyGroup Condition="'$(Configuration)|$(Platform)' == 'Debug|x64'">
     <DebugSymbols>true</DebugSymbols>
-    <OutputPath>..\..\bin\</OutputPath>
+    <OutputPath>..\..\..\..\trunk\sources\bin\</OutputPath>
     <DefineConstants>DEBUG;TRACE</DefineConstants>
     <DebugType>full</DebugType>
@@ -58 +58 @@
   </PropertyGroup>
   <PropertyGroup Condition="'$(Configuration)|$(Platform)' == 'Release|x64'">
-    <OutputPath>..\..\bin\</OutputPath>
+    <OutputPath>..\..\..\..\trunk\sources\bin\</OutputPath>
     <DefineConstants>TRACE</DefineConstants>
     <Optimize>true</Optimize>
@@ -76 +76 @@
   <PropertyGroup Condition="'$(Configuration)|$(Platform)' == 'Debug|x86'">
     <DebugSymbols>true</DebugSymbols>
-    <OutputPath>..\..\bin\</OutputPath>
+    <OutputPath>..\..\..\..\trunk\sources\bin\</OutputPath>
     <DefineConstants>DEBUG;TRACE</DefineConstants>
     <DebugType>full</DebugType>
@@ -92 +92 @@
   </PropertyGroup>
   <PropertyGroup Condition="'$(Configuration)|$(Platform)' == 'Release|x86'">
-    <OutputPath>..\..\bin\</OutputPath>
+    <OutputPath>..\..\..\..\trunk\sources\bin\</OutputPath>
     <DefineConstants>TRACE</DefineConstants>
     <Optimize>true</Optimize>
@@ -109 +109 @@
   </PropertyGroup>
   <ItemGroup>
+    <Reference Include="HeuristicLab.Common-3.3">
+      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Common-3.3.dll</HintPath>
+      <Private>False</Private>
+    </Reference>
+    <Reference Include="HeuristicLab.PluginInfrastructure-3.3">
+      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.PluginInfrastructure-3.3.dll</HintPath>
+      <Private>False</Private>
+    </Reference>
     <Reference Include="System" />
     <Reference Include="System.Core" />
@@ -115 +123 @@
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="MarsagliaRandom.cs" />
+    <Compile Include="TSPLIBHeterogeneousPTSPDataDescriptor.cs" />
+    <Compile Include="TSPLIBHomogeneousPTSPDataDescriptor.cs" />
+    <Compile Include="TSPLIBHeterogeneousPTSPInstanceProvider.cs" />
     <Compile Include="TSPLIBInstanceProvider.cs" />
     <Compile Include="TSPLIBATSPInstanceProvider.cs" />
     <Compile Include="TSPLIBCVRPInstanceProvider.cs" />
     <Compile Include="TSPLIBDataDescriptor.cs" />
+    <Compile Include="TSPLIBHomogeneousPTSPInstanceProvider.cs" />
     <Compile Include="TSPLIBTSPInstanceProvider.cs" />
     <Compile Include="TSPLIBParser.cs" />
@@ -134 +147 @@
   </ItemGroup>
   <ItemGroup>
-    <ProjectReference Include="..\..\HeuristicLab.Common\3.3\HeuristicLab.Common-3.3.csproj">
-      <Project>{A9AD58B9-3EF9-4CC1-97E5-8D909039FF5C}</Project>
-      <Name>HeuristicLab.Common-3.3</Name>
-      <Private>False</Private>
-    </ProjectReference>
-    <ProjectReference Include="..\..\HeuristicLab.PluginInfrastructure\3.3\HeuristicLab.PluginInfrastructure-3.3.csproj">
-      <Project>{94186A6A-5176-4402-AE83-886557B53CCA}</Project>
-      <Name>HeuristicLab.PluginInfrastructure-3.3</Name>
-      <Private>False</Private>
-    </ProjectReference>
     <ProjectReference Include="..\..\HeuristicLab.Problems.Instances\3.3\HeuristicLab.Problems.Instances-3.3.csproj">
-      <Project>{3540E29E-4793-49E7-8EE2-FEA7F61C3994}</Project>
+      <Project>{3540e29e-4793-49e7-8ee2-fea7f61c3994}</Project>
       <Name>HeuristicLab.Problems.Instances-3.3</Name>
       <Private>False</Private>
     </ProjectReference>
   </ItemGroup>
-  <ItemGroup />
   <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
   <PropertyGroup>

branches/PTSP/HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBATSPInstanceProvider.cs

@@ -36 +36 @@
     protected override string FileExtension { get { return "atsp"; } }
 
-    protected override ATSPData LoadInstance(TSPLIBParser parser) {
+    protected override ATSPData LoadInstance(TSPLIBParser parser, IDataDescriptor descriptor = null) {
       var instance = new ATSPData();
 

branches/PTSP/HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBCVRPInstanceProvider.cs

@@ -36 +36 @@
     protected override string FileExtension { get { return "vrp"; } }
 
-    protected override CVRPData LoadInstance(TSPLIBParser parser) {
+    protected override CVRPData LoadInstance(TSPLIBParser parser, IDataDescriptor descriptor = null) {
       parser.Parse();
       var instance = new CVRPData();

branches/PTSP/HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBHeterogeneousPTSPDataDescriptor.cs

@@ -20 +20 @@
 #endregion
 
+
 namespace HeuristicLab.Problems.Instances.TSPLIB {
-  internal class TSPLIBDataDescriptor : IDataDescriptor {
-    public string Name { get; internal set; }
-    public string Description { get; internal set; }
+  internal class TSPLIBHeterogeneousPTSPDataDescriptor : TSPLIBDataDescriptor {
+    public int Seed { get; internal set; }
 
-    internal string InstanceIdentifier { get; set; }
-    internal string SolutionIdentifier { get; set; }
-
-    internal TSPLIBDataDescriptor(string name, string description, string instanceIdentifier, string solutionIdentifier) {
+    internal TSPLIBHeterogeneousPTSPDataDescriptor(string name, string description, string instanceIdentifier, string solutionIdentifier, int seed)
+      : base(name, description, instanceIdentifier, solutionIdentifier) {
       this.Name = name;
       this.Description = description;
       this.InstanceIdentifier = instanceIdentifier;
       this.SolutionIdentifier = solutionIdentifier;
+      this.Seed = seed;
     }
   }

branches/PTSP/HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBHeterogeneousPTSPInstanceProvider.cs

@@ -21 +21 @@
 
 using System;
+using System.Collections.Generic;
 using System.IO;
 using System.Linq;
 
 namespace HeuristicLab.Problems.Instances.TSPLIB {
-  public class TSPLIBTSPInstanceProvider : TSPLIBInstanceProvider<TSPData> {
+  public class TSPLIBHeterogeneousPTSPInstanceProvider : TSPLIBInstanceProvider<PTSPData> {
 
     public override string Name {
-      get { return "TSPLIB (symmetric TSP)"; }
+      get { return "TSPLIB (heterogeneous symmetric PTSP)"; }
     }
 
@@ -37 +38 @@
     protected override string FileExtension { get { return "tsp"; } }
 
-    protected override TSPData LoadInstance(TSPLIBParser parser) {
+    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
+      foreach (var desc in base.GetDataDescriptors().OfType<TSPLIBDataDescriptor>()) {
+        desc.Name += " [0.1;0.9]";
+        desc.SolutionIdentifier = null;
+        yield return desc;
+      }
+    }
+
+    protected override PTSPData LoadInstance(TSPLIBParser parser, IDataDescriptor descriptor = null) {
       parser.Parse();
       if (parser.FixedEdges != null) throw new InvalidDataException("TSP instance " + parser.Name + " contains fixed edges which are not supported by HeuristicLab.");
-      var instance = new TSPData();
+      var instance = new PTSPData();
       instance.Dimension = parser.Dimension;
       instance.Coordinates = parser.Vertices != null ? parser.Vertices : parser.DisplayVertices;
@@ -73 +82 @@
         + Environment.NewLine + Environment.NewLine
         + GetInstanceDescription();
+
+      var random = new MarsagliaRandom((uint)(descriptor != null ? descriptor.Name : instance.Name).GetHashCode());
+      instance.Probabilities = Enumerable.Range(0, instance.Dimension).Select(_ => 0.1 + 0.9 * random.NextDouble()).ToArray();
+
       return instance;
     }
 
-    protected override void LoadSolution(TSPLIBParser parser, TSPData instance) {
+    protected override void LoadSolution(TSPLIBParser parser, PTSPData instance) {
       parser.Parse();
       instance.BestKnownTour = parser.Tour.FirstOrDefault();
     }
 
-    public TSPData LoadData(string tspFile, string tourFile, double? bestQuality) {
+    public PTSPData LoadData(string tspFile, string tourFile, double? bestQuality) {
       var data = LoadInstance(new TSPLIBParser(tspFile));
       if (!String.IsNullOrEmpty(tourFile)) {

branches/PTSP/HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBHomogeneousPTSPDataDescriptor.cs

@@ -21 +21 @@
 
 namespace HeuristicLab.Problems.Instances.TSPLIB {
-  internal class TSPLIBDataDescriptor : IDataDescriptor {
-    public string Name { get; internal set; }
-    public string Description { get; internal set; }
+  internal class TSPLIBHomogeneousPTSPDataDescriptor : TSPLIBDataDescriptor {
+    public double Probability { get; internal set; }
 
-    internal string InstanceIdentifier { get; set; }
-    internal string SolutionIdentifier { get; set; }
-
-    internal TSPLIBDataDescriptor(string name, string description, string instanceIdentifier, string solutionIdentifier) {
+    internal TSPLIBHomogeneousPTSPDataDescriptor(string name, string description, string instanceIdentifier, string solutionIdentifier, double probability)
+      : base(name, description, instanceIdentifier, solutionIdentifier) {
       this.Name = name;
       this.Description = description;
       this.InstanceIdentifier = instanceIdentifier;
       this.SolutionIdentifier = solutionIdentifier;
+      this.Probability = probability;
     }
   }

branches/PTSP/HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBHomogeneousPTSPInstanceProvider.cs

@@ -21 +21 @@
 
 using System;
+using System.Collections.Generic;
+using System.Globalization;
 using System.IO;
 using System.Linq;
 
 namespace HeuristicLab.Problems.Instances.TSPLIB {
-  public class TSPLIBTSPInstanceProvider : TSPLIBInstanceProvider<TSPData> {
+  public class TSPLIBHomogeneousPTSPInstanceProvider : TSPLIBInstanceProvider<PTSPData> {
+    private static readonly double[] probabilities = new[] { 0.1, 0.2, 0.4, 0.5, 0.6, 0.8, 0.9, 1.0 };
 
     public override string Name {
-      get { return "TSPLIB (symmetric TSP)"; }
+      get { return "TSPLIB (homogeneous symmetric PTSP)"; }
     }
 
@@ -37 +40 @@
     protected override string FileExtension { get { return "tsp"; } }
 
-    protected override TSPData LoadInstance(TSPLIBParser parser) {
+    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
+      var tspDescriptors = base.GetDataDescriptors().OfType<TSPLIBDataDescriptor>();
+      foreach (var desc in tspDescriptors) {
+        foreach (var p in probabilities) {
+          yield return new TSPLIBHomogeneousPTSPDataDescriptor(
+            desc.Name + "-" + p.ToString(CultureInfo.InvariantCulture.NumberFormat),
+            desc.Description,
+            desc.InstanceIdentifier,
+            p == 1.0 ? desc.SolutionIdentifier : null,
+            p);
+        }
+      }
+    }
+
+    protected override PTSPData LoadInstance(TSPLIBParser parser, IDataDescriptor descriptor = null) {
       parser.Parse();
       if (parser.FixedEdges != null) throw new InvalidDataException("TSP instance " + parser.Name + " contains fixed edges which are not supported by HeuristicLab.");
-      var instance = new TSPData();
+      var instance = new PTSPData();
       instance.Dimension = parser.Dimension;
       instance.Coordinates = parser.Vertices != null ? parser.Vertices : parser.DisplayVertices;
@@ -73 +90 @@
         + Environment.NewLine + Environment.NewLine
         + GetInstanceDescription();
+      var ptspDesc = descriptor as TSPLIBHomogeneousPTSPDataDescriptor;
+      instance.Probabilities = ptspDesc != null ? Enumerable.Range(0, instance.Dimension).Select(_ => ptspDesc.Probability).ToArray()
+                                                : Enumerable.Range(0, instance.Dimension).Select(_ => 0.5).ToArray();
+
       return instance;
     }
 
-    protected override void LoadSolution(TSPLIBParser parser, TSPData instance) {
+    protected override void LoadSolution(TSPLIBParser parser, PTSPData instance) {
       parser.Parse();
       instance.BestKnownTour = parser.Tour.FirstOrDefault();
     }
 
-    public TSPData LoadData(string tspFile, string tourFile, double? bestQuality) {
+    public PTSPData LoadData(string tspFile, string tourFile, double? bestQuality) {
       var data = LoadInstance(new TSPLIBParser(tspFile));
       if (!String.IsNullOrEmpty(tourFile)) {

branches/PTSP/HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBInstanceProvider.cs

@@ -45 +45 @@
     protected abstract string FileExtension { get; }
 
-    protected abstract T LoadInstance(TSPLIBParser parser);
+    protected abstract T LoadInstance(TSPLIBParser parser, IDataDescriptor descriptor = null);
     protected abstract void LoadSolution(TSPLIBParser parser, T instance);
 
@@ -74 +74 @@
         var stream = entry.Open();
         var parser = new TSPLIBParser(stream);
-        var instance = LoadInstance(parser);
+        var instance = LoadInstance(parser, id);
 
         if (!String.IsNullOrEmpty(descriptor.SolutionIdentifier)) {

branches/PTSP/HeuristicLab.Problems.Instances.TSPLIB/3.3/TSPLIBTSPInstanceProvider.cs

@@ -37 +37 @@
     protected override string FileExtension { get { return "tsp"; } }
 
-    protected override TSPData LoadInstance(TSPLIBParser parser) {
+    protected override TSPData LoadInstance(TSPLIBParser parser, IDataDescriptor descriptor = null) {
       parser.Parse();
       if (parser.FixedEdges != null) throw new InvalidDataException("TSP instance " + parser.Name + " contains fixed edges which are not supported by HeuristicLab.");