Changeset 7877

Timestamp:

05/23/12 16:25:40 (12 years ago)

Author:

abeham

Message:

#1856:

• Added Gilmore-Lawler lower bound

Location:

trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3

Files:

• BoundsCalculators (added)
• BoundsCalculators/GilmoreLawlerBoundCalculator.cs (added)
• HeuristicLab.Problems.QuadraticAssignment-3.3.csproj (modified) (2 diffs)
• Plugin.cs.frame (modified) (1 diff)
• QuadraticAssignmentProblem.cs (modified) (11 diffs)

trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/HeuristicLab.Problems.QuadraticAssignment-3.3.csproj

@@ -114 +114 @@
     <Compile Include="Analyzers\QAPAlleleFrequencyAnalyzer.cs" />
     <Compile Include="Analyzers\QAPPopulationDiversityAnalyzer.cs" />
+    <Compile Include="BoundsCalculators\GilmoreLawlerBoundCalculator.cs" />
     <Compile Include="Evaluators\QAPScrambleMoveEvaluator.cs" />
     <Compile Include="Evaluators\QAPSwap2MoveEvaluator.cs" />
@@ -202 +203 @@
       <Private>False</Private>
     </ProjectReference>
+    <ProjectReference Include="..\..\HeuristicLab.Problems.LinearAssignment\3.3\HeuristicLab.Problems.LinearAssignment-3.3.csproj">
+      <Project>{7250653F-DE83-4069-8D34-8050E8E45EA1}</Project>
+      <Name>HeuristicLab.Problems.LinearAssignment-3.3</Name>
+    </ProjectReference>
   </ItemGroup>
   <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />

trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/Plugin.cs.frame

@@ -37 +37 @@
   [PluginDependency("HeuristicLab.Persistence", "3.3")]
   [PluginDependency("HeuristicLab.Problems.Instances", "3.3")]
+  [PluginDependency("HeuristicLab.Problems.LinearAssignment", "3.3")]
   public class HeuristicLabProblemsQuadraticAssignmentPlugin : PluginBase { }
 }

trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/QuadraticAssignmentProblem.cs

@@ -60 +60 @@
       get { return (IValueParameter<DoubleMatrix>)Parameters["Distances"]; }
     }
+    public IValueParameter<DoubleValue> LowerBoundParameter {
+      get { return (IValueParameter<DoubleValue>)Parameters["LowerBound"]; }
+    }
+    public IValueParameter<DoubleValue> AverageQualityParameter {
+      get { return (IValueParameter<DoubleValue>)Parameters["AverageQuality"]; }
+    }
     #endregion
 
@@ -78 +84 @@
       get { return DistancesParameter.Value; }
       set { DistancesParameter.Value = value; }
+    }
+    public DoubleValue LowerBound {
+      get { return LowerBoundParameter.Value; }
+      set { LowerBoundParameter.Value = value; }
+    }
+    public DoubleValue AverageQuality {
+      get { return AverageQualityParameter.Value; }
+      set { AverageQualityParameter.Value = value; }
     }
 
@@ -105 +119 @@
       Parameters.Add(new ValueParameter<DoubleMatrix>("Weights", "The strength of the connection between the facilities.", new DoubleMatrix(5, 5)));
       Parameters.Add(new ValueParameter<DoubleMatrix>("Distances", "The distance matrix which can either be specified directly without the coordinates, or can be calculated automatically from the coordinates.", new DoubleMatrix(5, 5)));
+      Parameters.Add(new OptionalValueParameter<DoubleValue>("LowerBound", "The Gilmore-Lawler lower bound to the solution quality."));
+      Parameters.Add(new OptionalValueParameter<DoubleValue>("AverageQuality", "The expected quality of a random solution."));
 
       Maximization.Value = false;
       MaximizationParameter.Hidden = true;
 
+      WeightsParameter.GetsCollected = false;
       Weights = new DoubleMatrix(new double[,] {
         { 0, 1, 0, 0, 1 },
@@ -117 +134 @@
       });
 
+      DistancesParameter.GetsCollected = false;
       Distances = new DoubleMatrix(new double[,] {
         {   0, 360, 582, 582, 360 },
@@ -153 +171 @@
         Parameters.Add(new ValueParameter<DoubleMatrix>("Distances", "The distance matrix which can either be specified directly without the coordinates, or can be calculated automatically from the coordinates.", d));
       }
+      if (!Parameters.ContainsKey("LowerBound")) {
+        Parameters.Add(new OptionalValueParameter<DoubleValue>("LowerBound", "The Gilmore-Lawler lower bound to the solution quality."));
+        LowerBound = new DoubleValue(GilmoreLawlerBoundCalculator.CalculateLowerBound(Weights, Distances));
+      }
+      if (!Parameters.ContainsKey("AverageQuality")) {
+        Parameters.Add(new OptionalValueParameter<DoubleValue>("AverageQuality", "The expected quality of a random solution."));
+        AverageQuality = new DoubleValue(Weights.Average() * Distances.Average() * Weights.Rows * Weights.Rows);
+      }
+      #endregion
       RegisterEventHandlers();
-      #endregion
     }
 
@@ -186 +212 @@
       Weights.RowsChanged += new EventHandler(Weights_RowsChanged);
       Weights.ColumnsChanged += new EventHandler(Weights_ColumnsChanged);
+      Weights.ToStringChanged += new EventHandler(Weights_ToStringChanged);
       ParameterizeSolutionCreator();
       ParameterizeEvaluator();
@@ -211 +238 @@
       }
     }
+    private void Weights_ToStringChanged(object sender, EventArgs e) {
+      UpdateParameterValues();
+    }
     private void DistancesParameter_ValueChanged(object sender, EventArgs e) {
       Distances.RowsChanged += new EventHandler(Distances_RowsChanged);
       Distances.ColumnsChanged += new EventHandler(Distances_ColumnsChanged);
+      Distances.ToStringChanged += new EventHandler(Distances_ToStringChanged);
       ParameterizeSolutionCreator();
       ParameterizeEvaluator();
@@ -239 +270 @@
       }
     }
+    private void Distances_ToStringChanged(object sender, EventArgs e) {
+      UpdateParameterValues();
+    }
     #endregion
 
-    #region Helpers
     private void RegisterEventHandlers() {
       SolutionCreator.PermutationParameter.ActualNameChanged += new EventHandler(SolutionCreator_PermutationParameter_ActualNameChanged);
@@ -248 +281 @@
       Weights.RowsChanged += new EventHandler(Weights_RowsChanged);
       Weights.ColumnsChanged += new EventHandler(Weights_ColumnsChanged);
+      Weights.ToStringChanged += new EventHandler(Weights_ToStringChanged);
       DistancesParameter.ValueChanged += new EventHandler(DistancesParameter_ValueChanged);
       Distances.RowsChanged += new EventHandler(Distances_RowsChanged);
       Distances.ColumnsChanged += new EventHandler(Distances_ColumnsChanged);
-    }
-
+      Distances.ToStringChanged += new EventHandler(Distances_ToStringChanged);
+    }
+
+    #region Helpers
     private void InitializeOperators() {
       var defaultOperators = new HashSet<IPermutationOperator>(new IPermutationOperator[] {
@@ -363 +399 @@
       }
     }
+
+    private void UpdateParameterValues() {
+      LowerBound = new DoubleValue(GilmoreLawlerBoundCalculator.CalculateLowerBound(Weights, Distances));
+      AverageQuality = new DoubleValue(Weights.Average() * Distances.Average() * Weights.Rows * Weights.Rows);
+    }
     #endregion
 
@@ -407 +448 @@
       BestKnownSolution = null;
       BestKnownSolutions = null;
+      UpdateParameterValues();
     }