Changeset 7593 for branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment

Timestamp:

03/11/12 10:54:36 (13 years ago)

Author:

abeham

Message:

#1614

• Investigation in different solution creator that result in feasible solutions even for 95% fill level instances
• Added option for all solution creators to produce the least infeasible solution if no feasible solution could be found
• Added maximum tries parameter to all creators

Location:

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3

Files:

• Evaluators/GQAPEvaluator.cs (modified) (1 diff)
• HeuristicLab.Problems.GeneralizedQuadraticAssignment-3.3.csproj (modified) (1 diff)
• SolutionCreators/GreedyRandomizedSolutionCreator.cs (modified) (6 diffs)
• SolutionCreators/RandomButFeasibleSolutionCreator.cs (added)
• SolutionCreators/RandomSolutionCreator.cs (modified) (1 diff)
• SolutionCreators/SlackMinimizationSolutionCreator.cs (added)

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Evaluators/GQAPEvaluator.cs

@@ -132 +132 @@
         slack[assignment[i]] -= demands[i];
       }
-      overbookedCapacity = slack.Select((v, i) => new { V = v, Index = i }).Where(x => x.V < 0.0).Select(x => -x.V / capacities[x.Index]).Sum();
+      overbookedCapacity = EvaluateOverbooking(slack, capacities);
+    }
+
+    public static double EvaluateOverbooking(DoubleArray slack, DoubleArray capacities) {
+      return slack.Select((v, i) => new { V = v, Index = i }).Where(x => x.V < 0.0).Select(x => -x.V / capacities[x.Index]).Sum();
     }
 

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/HeuristicLab.Problems.GeneralizedQuadraticAssignment-3.3.csproj

@@ -104 +104 @@
     <Compile Include="GQAPAssignment.cs" />
     <Compile Include="Operators\Crossovers\CordeauCrossover.cs" />
+    <Compile Include="SolutionCreators\SlackMinimizationSolutionCreator.cs" />
+    <Compile Include="SolutionCreators\RandomButFeasibleSolutionCreator.cs" />
     <Compile Include="SolutionCreators\GQAPSolutionCreator.cs" />
     <Compile Include="SolutionCreators\GQAPStochasticSolutionCreator.cs" />

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/SolutionCreators/GreedyRandomizedSolutionCreator.cs

@@ -23 +23 @@
 using System.Collections.Generic;
 using System.Linq;
+using System.Threading;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -39 +40 @@
       get { return (IValueLookupParameter<IntValue>)Parameters["MaximumTries"]; }
     }
+    public IValueLookupParameter<BoolValue> CreateMostFeasibleSolutionParameter {
+      get { return (IValueLookupParameter<BoolValue>)Parameters["CreateMostFeasibleSolution"]; }
+    }
 
     [StorableConstructor]
@@ -46 +50 @@
     public GreedyRandomizedSolutionCreator()
       : base() {
-      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumTries", "The maximum number of tries to create a feasible solution.", new IntValue(10000)));
+      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumTries", "The maximum number of tries to create a feasible solution after which an exception is thrown. If it is set to 0 or a negative value there will be an infinite number of attempts.", new IntValue(100000)));
+      Parameters.Add(new ValueLookupParameter<BoolValue>("CreateMostFeasibleSolution", "If this is set to true the operator will always succeed, and outputs the solution with the least violation instead of throwing an exception.", new BoolValue(false)));
     }
 
@@ -53 +58 @@
     }
 
-    protected override IntegerVector CreateRandomSolution(IRandom random, DoubleArray demands, DoubleArray capacities) {
-      int tries = 0, maxTries = MaximumTriesParameter.ActualValue.Value;
-      var assignment = new Dictionary<int, int>();
-      var slack = new Dictionary<int, double>();
-
-      while (tries < maxTries) {
-        assignment.Clear();
-        slack = capacities.Select((v, i) => new { Index = i, Value = v }).ToDictionary(x => x.Index, y => y.Value);
-        HashSet<int> CF = new HashSet<int>(), // set of chosen facilities / equipments
+    public static IntegerVector CreateSolution(IRandom random, DoubleArray demands, DoubleArray capacities, int maximumTries, bool createMostFeasibleSolution, CancellationToken cancelToken) {
+      int tries = 0;
+      var assignment = new Dictionary<int, int>(demands.Length);
+      DoubleArray slack = new DoubleArray(capacities.Length);
+      double minViolation = double.MaxValue;
+      Dictionary<int, int> bestAssignment = null;
+      HashSet<int> CF = new HashSet<int>(), // set of chosen facilities / equipments
           T = new HashSet<int>(), // set of facilities / equpiments that can be assigned to the set of chosen locations (CL)
           CL = new HashSet<int>(), // set of chosen locations
           F = new HashSet<int>(Enumerable.Range(0, demands.Length)), // set of (initially) all facilities / equipments
           L = new HashSet<int>(Enumerable.Range(0, capacities.Length)); // set of (initially) all locations
+
+      while (maximumTries <= 0 || tries < maximumTries) {
+        cancelToken.ThrowIfCancellationRequested();
+
+        assignment.Clear();
+        for (int i = 0; i < capacities.Length; i++) slack[i] = capacities[i];
+        CF.Clear();
+        T.Clear();
+        CL.Clear();
+        F.Clear(); F.UnionWith(Enumerable.Range(0, demands.Length));
+        L.Clear(); L.UnionWith(Enumerable.Range(0, capacities.Length));
 
         double threshold = 1.0;
@@ -87 +101 @@
           }
         } while (T.Any() || L.Any());
-        tries++;
-        if (!F.Any()) break;
+        if (maximumTries > 0) tries++;
+        if (!F.Any()) {
+          bestAssignment = assignment;
+          break;
+        } else if (createMostFeasibleSolution) {
+          // complete the solution and remember the one with least violation
+          while (F.Any()) {
+            var f = F.ChooseMax(x => demands[x]);
+            var l = L.ChooseMax(x => slack[x]);
+            F.Remove(f);
+            assignment.Add(f, l);
+            slack[l] -= demands[f];
+          }
+          double violation = GQAPEvaluator.EvaluateOverbooking(slack, capacities);
+          if (violation < minViolation) {
+            bestAssignment = assignment;
+            assignment = new Dictionary<int, int>(demands.Length);
+            minViolation = violation;
+          }
+        }
       }
 
-      if (assignment.Count != demands.Length) throw new InvalidOperationException(String.Format("No solution could be found in {0} tries.", maxTries));
+      if (bestAssignment == null || bestAssignment.Count != demands.Length) throw new InvalidOperationException(String.Format("No solution could be found in {0} tries.", maximumTries));
 
-      return new IntegerVector(assignment.OrderBy(x => x.Key).Select(x => x.Value).ToArray());
+      return new IntegerVector(bestAssignment.OrderBy(x => x.Key).Select(x => x.Value).ToArray());
+    }
+
+    protected override IntegerVector CreateRandomSolution(IRandom random, DoubleArray demands, DoubleArray capacities) {
+      return CreateSolution(random, demands, capacities,
+        MaximumTriesParameter.ActualValue.Value,
+        CreateMostFeasibleSolutionParameter.ActualValue.Value,
+        CancellationToken);
     }
 
@@ -102 +141 @@
     }
 
-    private static double GetMaximumSlack(Dictionary<int, double> slack, HashSet<int> CL) {
-      return slack.Where(x => CL.Contains(x.Key)).Select(x => x.Value).Max();
+    private static double GetMaximumSlack(DoubleArray slack, HashSet<int> CL) {
+      return slack.Select((val, idx) => new { idx, val }).Where(x => CL.Contains(x.idx)).Select(x => x.val).Max();
     }
 
-    private static IEnumerable<int> WithSlackGreaterOrEqual(HashSet<int> locations, double minimum, Dictionary<int, double> slack) {
+    private static IEnumerable<int> WithSlackGreaterOrEqual(HashSet<int> locations, double minimum, DoubleArray slack) {
       foreach (int l in locations) {
         if (slack[l] >= minimum) yield return l;

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/SolutionCreators/RandomSolutionCreator.cs

@@ -40 +40 @@
     }
 
+    public static IntegerVector CreateSolution(IRandom random, DoubleArray demands, DoubleArray capacities) {
+      return UniformRandomIntegerVectorCreator.Apply(random, demands.Length, 0, capacities.Length);
+    }
+
     protected override IntegerVector CreateRandomSolution(IRandom random, DoubleArray demands, DoubleArray capacities) {
-      return UniformRandomIntegerVectorCreator.Apply(random, demands.Length, 0, capacities.Length);
+      return CreateSolution(random, demands, capacities);
     }
   }