Changeset 15758 for branches/1614_GeneralizedQAP

Timestamp:

02/12/18 16:53:23 (7 years ago)

Author:

abeham

Message:

#1614: Added LocalSolver model based on lists

Location:

branches/1614_GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3

Files:

• HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms-3.3.csproj (modified) (1 diff)
• LocalSolverNet/GQAPListSolver.cs (copied) (copied from branches/1614_GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LocalSolverNet/GQAPBinarySolver.cs) (8 diffs)

branches/1614_GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms-3.3.csproj

@@ -130 +130 @@
     <Compile Include="LocalSearch\IteratedLS.cs" />
     <Compile Include="LocalSearch\MultistartLS.cs" />
+    <Compile Include="LocalSolverNet\GQAPListSolver.cs" />
     <Compile Include="LocalSolverNet\GQAPIntegerSolver.cs" />
     <Compile Include="LocalSolverNet\LocalSolverContext.cs" />

branches/1614_GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LocalSolverNet/GQAPListSolver.cs

@@ -31 +31 @@
 
 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LocalSolverNet {
-  [Item("LocalSolver Binary (GQAP)", "LocalSolver algorithm solving the GQAP using 0-1 decision variables")]
+  [Item("LocalSolver List (GQAP)", "LocalSolver algorithm solving the GQAP using list decision variables")]
   [StorableClass]
   [Creatable(CreatableAttribute.Categories.Algorithms)]
-  public sealed class GQAPBinarySolver : ContextAlgorithm<LocalSolverContext, IntegerVectorEncoding> {
+  public sealed class GQAPListSolver : ContextAlgorithm<LocalSolverContext, IntegerVectorEncoding> {
     public override bool SupportsPause {
       get { return false; }
@@ -49 +49 @@
 
     // LS Program variables
-    private LSExpression[][] x;
+    private LSExpression[] x;
     private LSExpression[] equipmentsOnLocations;
     private LSExpression obj;
@@ -56 +56 @@
 
     [StorableConstructor]
-    private GQAPBinarySolver(bool deserializing) : base(deserializing) { }
-    private GQAPBinarySolver(GQAPBinarySolver original, Cloner cloner)
+    private GQAPListSolver(bool deserializing) : base(deserializing) { }
+    private GQAPListSolver(GQAPListSolver original, Cloner cloner)
     : base(original, cloner) {
     }
-    public GQAPBinarySolver() {
+    public GQAPListSolver() {
       Problem = new GQAP();
       MaximumEvaluationsParameter.Hidden = true;
@@ -67 +67 @@
 
     public override IDeepCloneable Clone(Cloner cloner) {
-      return new GQAPBinarySolver(this, cloner);
+      return new GQAPListSolver(this, cloner);
     }
 
@@ -107 +107 @@
       var locations = Problem.ProblemInstance.Capacities.Length;
       var best = new int[Problem.ProblemInstance.Demands.Length];
-      for (var i = 0; i < best.Length; i++) {
-        for (var j = 0; j < locations; j++) {
-          if (x[i][j].GetIntValue() == 1) {
-            best[i] = j;
-            break;
-          }
+      for (var j = 0; j < locations; j++) {
+        var xcol = x[j].GetCollectionValue();
+        for (var i = 0; i < xcol.Count(); i++) {
+          var equip = xcol.Get(i);
+          best[equip] = j;
         }
       }
@@ -140 +139 @@
 
       // Declares the optimization model
-      LSModel model = localSolver.GetModel();
+      var model = localSolver.GetModel();
 
       var data = Problem.ProblemInstance;
 
+      x = new LSExpression[data.Capacities.Length];
       // x[f,l] = 1 if equipments f is on location l, 0 otherwise
-      x = new LSExpression[data.Demands.Length][];
-      for (int f = 0; f < data.Demands.Length; f++) {
-        x[f] = new LSExpression[data.Capacities.Length];
-        for (int l = 0; l < data.Capacities.Length; l++) {
-          x[f][l] = model.Bool();
+      for (int r = 0; r < data.Capacities.Length; r++) {
+        x[r] = model.List(data.Demands.Length);
+      }
+
+      // All equipments are installed in exactly 1 location
+      model.Constraint(model.Partition(x));
+
+      var demandsArray = model.Array(data.Demands);
+
+      // Create distances as an array to be accessed by an at operator
+      var weightsJagged = new double[data.Demands.Length][];
+      for (var i = 0; i < data.Demands.Length; i++) {
+        weightsJagged[i] = new double[data.Demands.Length];
+        for (var j = 0; j < data.Demands.Length; j++) {
+          weightsJagged[i][j] = data.Weights[i, j];
         }
       }
-
-      // All equipments are installed in exactly 1 location
-      for (int f = 0; f < data.Demands.Length; f++) {
-        LSExpression nbLocationsAssigned = model.Sum();
-        for (int l = 0; l < data.Capacities.Length; l++) {
-          nbLocationsAssigned.AddOperand(x[f][l]);
-        }
-        model.Constraint(nbLocationsAssigned == 1);
-      }
-
-      // All locations contain not more equipments than there is capacity for
-      for (int l = 0; l < data.Capacities.Length; l++) {
-        LSExpression assignedDemand = model.Sum();
-        for (int f = 0; f < data.Demands.Length; f++) {
-          assignedDemand.AddOperand(x[f][l] * data.Demands[f]);
-        }
-        model.Constraint(assignedDemand <= data.Capacities[l]);
-      }
-
-      // Index of the assigned location of equipment f
-      equipmentsOnLocations = new LSExpression[data.Demands.Length];
-      for (int f = 0; f < data.Demands.Length; f++) {
-        equipmentsOnLocations[f] = model.Sum();
-        for (int l = 0; l < data.Capacities.Length; l++) {
-          equipmentsOnLocations[f].AddOperand(l * x[f][l]);
-        }
-      }
-
-      // Create distances as an array to be accessed by an at operator
       var distancesJagged = new double[data.Capacities.Length][];
       for (var i = 0; i < data.Capacities.Length; i++) {
@@ -193 +174 @@
           installJagged[i][j] = data.InstallationCosts[i, j];
       }
-      LSExpression distancesArray = model.Array(distancesJagged);
-      LSExpression installCostsArray = model.Array(installJagged);
-
-      // Minimize the sum of product distance*flow
+      var weightsArray = model.Array(weightsJagged);
+      var distancesArray = model.Array(distancesJagged);
+      var installCostsArray = model.Array(installJagged);
+
       obj = model.Sum();
-      for (int f1 = 0; f1 < data.Demands.Length; f1++) {
-        for (int f2 = 0; f2 < data.Demands.Length; f2++) {
-          obj.AddOperand(data.TransportationCosts * data.Weights[f1, f2] * distancesArray[equipmentsOnLocations[f1], equipmentsOnLocations[f2]]);
+      // All locations contain not more equipments than there is capacity for
+      for (int l = 0; l < data.Capacities.Length; l++) {
+        var c = model.Count(x[l]);
+        var demandSelector = model.Function(i => demandsArray[x[l][i]]);
+        var assignedDemand = model.Sum(model.Range(0, c), demandSelector);
+        model.Constraint(assignedDemand <= data.Capacities[l]);
+
+        var installCostSelector = model.Function(i => installCostsArray[x[l][i], l]);
+        var installCosts = model.Sum(model.Range(0, c), installCostSelector);
+        obj.AddOperand(installCosts);
+        
+        // Flow to other equipments
+        for (int k = 0; k < data.Capacities.Length; k++) {
+          var kc = model.Count(x[k]);
+          var flowCostSelector = model.Function(j => model.Sum(model.Range(0, c), model.Function(i => weightsArray[x[l][i], x[k][j]] * distancesArray[l, k] * data.TransportationCosts)));
+          obj.AddOperand(model.Sum(model.Range(0, kc), flowCostSelector));
         }
-        obj.AddOperand(installCostsArray[f1, equipmentsOnLocations[f1]]);
-      }
-
-      model.Minimize(obj);
+      }
+
+      model.Minimize(this.obj);
 
       try {
@@ -218 +211 @@
         localSolver.Solve();
 
-        var curObj = obj.GetDoubleValue();
+        var curObj = this.obj.GetDoubleValue();
         if (curObj < prevObj)
           UpdateSolution(curObj);