Changeset 5814 for branches/QAP/HeuristicLab.Problems.QuadraticAssignment

Timestamp:

03/23/11 12:03:24 (14 years ago)

Author:

abeham

Message:

#1330

• Added a test if the reported quality of the solution instances is similar to the evaluated qualities of these solutions
• Adapted parsing of the solution file and added another parameter whether the permutation should be treated as facility->location (HeuristicLab default) or location->facility.
• Adapted QuadraticAssignmentProblem to use that method that corresponds with the reported quality since there is no consistent encoding over all files
• Improved API documentation of the parsing methods

Location:

branches/QAP/HeuristicLab.Problems.QuadraticAssignment/3.3

Files:

• Parsers/QAPLIBSolutionParser.cs (modified) (6 diffs)
• QuadraticAssignmentProblem.cs (modified) (1 diff)
• Tests/QAPLIBInstancesTest.cs (modified) (2 diffs)

branches/QAP/HeuristicLab.Problems.QuadraticAssignment/3.3/Parsers/QAPLIBSolutionParser.cs

@@ -1 +1 @@
 using System;
+using System.Globalization;
 using System.IO;
 
@@ -6 +7 @@
     public int Size { get; private set; }
     public int[] Assignment { get; private set; }
-    public double Qualiy { get; private set; }
+    public double Quality { get; private set; }
     public Exception Error { get; private set; }
 
@@ -16 +17 @@
       Size = 0;
       Assignment = null;
-      Qualiy = double.NaN;
+      Quality = double.NaN;
       Error = null;
     }
 
-    public bool Parse(string file) {
+    /// <summary>
+    /// Reads from the given stream data which is expected to be in the QAPLIB solution format.
+    /// 
+    /// The QAPLIB solution file format (.sln) is as follows:
+    /// First line: Size of the permutation followed by a blank followed by the quality formatted using no thousands separator and if a fractional number with the "." as decimal symbol
+    /// Remaining lines: The values of the permutation separated by blanks. Values must lie in the range [1;size of the permutation].
+    /// </summary>
+    /// <param name="file">The file to read data from.</param>
+    /// <param name="valueAsLocation">The numbers can be interpreted either as facilities or locations.
+    /// HeuristicLab always encodes the permutation such that the index denotes the facility and the value the location.
+    /// If this parameter is true, then the permutation is expected to follow this encoding.
+    /// If this parameter is false, the meaning of value and index will be swapped when reading the permutation.</param>
+    /// <returns></returns>
+    public bool Parse(string file, bool valueAsLocation) {
       using (Stream stream = new FileStream(file, FileMode.Open, FileAccess.Read)) {
-        return Parse(stream);
+        return Parse(stream, valueAsLocation);
       }
     }
 
     /// <summary>
-    /// Reads from the given stream data which is expected to be in the QAPLIB format.
+    /// Reads from the given stream data which is expected to be in the QAPLIB solution format.
+    /// 
+    /// The QAPLIB solution file format (.sln) is as follows:
+    /// First line: Size of the permutation followed by a blank followed by the quality formatted using no thousands separator and if a fractional number with the "." as decimal symbol
+    /// Remaining lines: The values of the permutation separated by blanks. Values must lie in the range [1;size of the permutation].
     /// </summary>
     /// <remarks>
@@ -33 +51 @@
     /// </remarks>
     /// <param name="stream">The stream to read data from.</param>
+    /// <param name="valueAsLocation">The numbers can be interpreted either as facilities or locations.
+    /// HeuristicLab always encodes the permutation such that the index denotes the facility and the value the location.
+    /// If this parameter is true, then the permutation is expected to follow this encoding.
+    /// If this parameter is false, the meaning of value and index will be swapped when reading the permutation.</param>
     /// <returns>True if the file was successfully read or false otherwise.</returns>
-    public bool Parse(Stream stream) {
+    public bool Parse(Stream stream, bool valueAsLocation) {
       Error = null;
       try {
@@ -41 +63 @@
         string[] firstline = reader.ReadLine().Split(delim, StringSplitOptions.RemoveEmptyEntries);
         Size = int.Parse(firstline[0]);
-        Qualiy = double.Parse(firstline[1]);
+        Quality = double.Parse(firstline[1], CultureInfo.InvariantCulture.NumberFormat);
         Assignment = new int[Size];
         int read = 0;
@@ -48 +70 @@
           string[] vals = valLine.Split(delim, StringSplitOptions.RemoveEmptyEntries);
           for (int j = 0; j < vals.Length; j++) {
-            Assignment[read++] = int.Parse(vals[j]);
+            if (valueAsLocation)
+              Assignment[int.Parse(vals[j]) - 1] = read++;
+            else Assignment[read++] = int.Parse(vals[j]) - 1;
           }
         }

branches/QAP/HeuristicLab.Problems.QuadraticAssignment/3.3/QuadraticAssignmentProblem.cs

@@ -325 +325 @@
           .GetManifestResourceStream(InstancePrefix + instance + ".sln")) {
           QAPLIBSolutionParser solParser = new QAPLIBSolutionParser();
-          solParser.Parse(solStream);
+          solParser.Parse(solStream, false); // most sln's seem to be of the type index = location => value = facility
           if (solParser.Error != null) throw solParser.Error;
-          BestKnownQuality = new DoubleValue(solParser.Qualiy);
-          BestKnownSolution = new Permutation(PermutationTypes.Absolute, solParser.Assignment);
+          if (!solParser.Quality.IsAlmost(QAPEvaluator.Apply(new Permutation(PermutationTypes.Absolute, solParser.Assignment), Weights, DistanceMatrix))) {
+            solStream.Seek(0, SeekOrigin.Begin);
+            solParser.Parse(solStream, true); // some sln's seem to be of the type index = facility => value = location
+            if (solParser.Error != null) throw solParser.Error;
+            if (solParser.Quality.IsAlmost(QAPEvaluator.Apply(new Permutation(PermutationTypes.Absolute, solParser.Assignment), Weights, DistanceMatrix))) {
+              BestKnownQuality = new DoubleValue(solParser.Quality);
+              BestKnownSolution = new Permutation(PermutationTypes.Absolute, solParser.Assignment);
+            } else {
+              BestKnownQuality = null;
+              BestKnownSolution = null;
+            }
+          } else {
+            BestKnownQuality = new DoubleValue(solParser.Quality);
+            BestKnownSolution = new Permutation(PermutationTypes.Absolute, solParser.Assignment);
+          }
         }
       } else {

branches/QAP/HeuristicLab.Problems.QuadraticAssignment/3.3/Tests/QAPLIBInstancesTest.cs

@@ -1 +1 @@
 using System;
 using System.Text;
+using HeuristicLab.Common;
 using HeuristicLab.Problems.QuadraticAssignment;
 using Microsoft.VisualStudio.TestTools.UnitTesting;
@@ -20 +21 @@
       Assert.IsTrue(failedInstances.Length == 0, "Following instances failed to load: " + Environment.NewLine + failedInstances.ToString());
     }
+
+    [TestMethod]
+    public void TestReportedSolutionQuality() {
+      StringBuilder failedInstances = new StringBuilder();
+      QuadraticAssignmentProblem qap = new QuadraticAssignmentProblem();
+      foreach (string instance in qap.EmbeddedInstances) {
+        try {
+          qap.LoadEmbeddedInstance(instance);
+        } catch {
+          Assert.Fail("Not all instances load correctly");
+        }
+        if (qap.BestKnownSolution != null) {
+          double quality = double.NaN;
+          try {
+            quality = QAPEvaluator.Apply(qap.BestKnownSolution, qap.Weights, qap.DistanceMatrix);
+          } catch (Exception ex) {
+            failedInstances.AppendLine("An unknown problem occurred evaluating solution of instance " + instance + ": " + ex.Message);
+          }
+          if (!quality.IsAlmost(qap.BestKnownQuality.Value)) {
+            failedInstances.AppendLine(instance + ": Reported quality: " + qap.BestKnownQuality.Value.ToString() + ", evaluated fitness: " + quality.ToString() + ".");
+          }
+        }
+
+      }
+      Assert.IsTrue(failedInstances.Length == 0, "Following instances report divergent fitness values: " + Environment.NewLine + failedInstances.ToString());
+    }
   }
 }