Changeset 15758
 Timestamp:
 02/12/18 16:53:23 (7 years ago)
 Location:
 branches/1614_GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3
 Files:

 1 edited
 1 copied
Legend:
 Unmodified
 Added
 Removed

branches/1614_GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms3.3.csproj
r15719 r15758 130 130 <Compile Include="LocalSearch\IteratedLS.cs" /> 131 131 <Compile Include="LocalSearch\MultistartLS.cs" /> 132 <Compile Include="LocalSolverNet\GQAPListSolver.cs" /> 132 133 <Compile Include="LocalSolverNet\GQAPIntegerSolver.cs" /> 133 134 <Compile Include="LocalSolverNet\LocalSolverContext.cs" /> 
branches/1614_GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms/3.3/LocalSolverNet/GQAPListSolver.cs
r15717 r15758 31 31 32 32 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LocalSolverNet { 33 [Item("LocalSolver Binary (GQAP)", "LocalSolver algorithm solving the GQAP using 01decision variables")]33 [Item("LocalSolver List (GQAP)", "LocalSolver algorithm solving the GQAP using list decision variables")] 34 34 [StorableClass] 35 35 [Creatable(CreatableAttribute.Categories.Algorithms)] 36 public sealed class GQAP BinarySolver : ContextAlgorithm<LocalSolverContext, IntegerVectorEncoding> {36 public sealed class GQAPListSolver : ContextAlgorithm<LocalSolverContext, IntegerVectorEncoding> { 37 37 public override bool SupportsPause { 38 38 get { return false; } … … 49 49 50 50 // LS Program variables 51 private LSExpression[] []x;51 private LSExpression[] x; 52 52 private LSExpression[] equipmentsOnLocations; 53 53 private LSExpression obj; … … 56 56 57 57 [StorableConstructor] 58 private GQAP BinarySolver(bool deserializing) : base(deserializing) { }59 private GQAP BinarySolver(GQAPBinarySolver original, Cloner cloner)58 private GQAPListSolver(bool deserializing) : base(deserializing) { } 59 private GQAPListSolver(GQAPListSolver original, Cloner cloner) 60 60 : base(original, cloner) { 61 61 } 62 public GQAP BinarySolver() {62 public GQAPListSolver() { 63 63 Problem = new GQAP(); 64 64 MaximumEvaluationsParameter.Hidden = true; … … 67 67 68 68 public override IDeepCloneable Clone(Cloner cloner) { 69 return new GQAP BinarySolver(this, cloner);69 return new GQAPListSolver(this, cloner); 70 70 } 71 71 … … 107 107 var locations = Problem.ProblemInstance.Capacities.Length; 108 108 var best = new int[Problem.ProblemInstance.Demands.Length]; 109 for (var i = 0; i < best.Length; i++) { 110 for (var j = 0; j < locations; j++) { 111 if (x[i][j].GetIntValue() == 1) { 112 best[i] = j; 113 break; 114 } 109 for (var j = 0; j < locations; j++) { 110 var xcol = x[j].GetCollectionValue(); 111 for (var i = 0; i < xcol.Count(); i++) { 112 var equip = xcol.Get(i); 113 best[equip] = j; 115 114 } 116 115 } … … 140 139 141 140 // Declares the optimization model 142 LSModelmodel = localSolver.GetModel();141 var model = localSolver.GetModel(); 143 142 144 143 var data = Problem.ProblemInstance; 145 144 145 x = new LSExpression[data.Capacities.Length]; 146 146 // x[f,l] = 1 if equipments f is on location l, 0 otherwise 147 x = new LSExpression[data.Demands.Length][]; 148 for (int f = 0; f < data.Demands.Length; f++) { 149 x[f] = new LSExpression[data.Capacities.Length]; 150 for (int l = 0; l < data.Capacities.Length; l++) { 151 x[f][l] = model.Bool(); 147 for (int r = 0; r < data.Capacities.Length; r++) { 148 x[r] = model.List(data.Demands.Length); 149 } 150 151 // All equipments are installed in exactly 1 location 152 model.Constraint(model.Partition(x)); 153 154 var demandsArray = model.Array(data.Demands); 155 156 // Create distances as an array to be accessed by an at operator 157 var weightsJagged = new double[data.Demands.Length][]; 158 for (var i = 0; i < data.Demands.Length; i++) { 159 weightsJagged[i] = new double[data.Demands.Length]; 160 for (var j = 0; j < data.Demands.Length; j++) { 161 weightsJagged[i][j] = data.Weights[i, j]; 152 162 } 153 163 } 154 155 // All equipments are installed in exactly 1 location156 for (int f = 0; f < data.Demands.Length; f++) {157 LSExpression nbLocationsAssigned = model.Sum();158 for (int l = 0; l < data.Capacities.Length; l++) {159 nbLocationsAssigned.AddOperand(x[f][l]);160 }161 model.Constraint(nbLocationsAssigned == 1);162 }163 164 // All locations contain not more equipments than there is capacity for165 for (int l = 0; l < data.Capacities.Length; l++) {166 LSExpression assignedDemand = model.Sum();167 for (int f = 0; f < data.Demands.Length; f++) {168 assignedDemand.AddOperand(x[f][l] * data.Demands[f]);169 }170 model.Constraint(assignedDemand <= data.Capacities[l]);171 }172 173 // Index of the assigned location of equipment f174 equipmentsOnLocations = new LSExpression[data.Demands.Length];175 for (int f = 0; f < data.Demands.Length; f++) {176 equipmentsOnLocations[f] = model.Sum();177 for (int l = 0; l < data.Capacities.Length; l++) {178 equipmentsOnLocations[f].AddOperand(l * x[f][l]);179 }180 }181 182 // Create distances as an array to be accessed by an at operator183 164 var distancesJagged = new double[data.Capacities.Length][]; 184 165 for (var i = 0; i < data.Capacities.Length; i++) { … … 193 174 installJagged[i][j] = data.InstallationCosts[i, j]; 194 175 } 195 LSExpression distancesArray = model.Array(distancesJagged);196 LSExpression installCostsArray = model.Array(installJagged);197 198 // Minimize the sum of product distance*flow 176 var weightsArray = model.Array(weightsJagged); 177 var distancesArray = model.Array(distancesJagged); 178 var installCostsArray = model.Array(installJagged); 179 199 180 obj = model.Sum(); 200 for (int f1 = 0; f1 < data.Demands.Length; f1++) { 201 for (int f2 = 0; f2 < data.Demands.Length; f2++) { 202 obj.AddOperand(data.TransportationCosts * data.Weights[f1, f2] * distancesArray[equipmentsOnLocations[f1], equipmentsOnLocations[f2]]); 181 // All locations contain not more equipments than there is capacity for 182 for (int l = 0; l < data.Capacities.Length; l++) { 183 var c = model.Count(x[l]); 184 var demandSelector = model.Function(i => demandsArray[x[l][i]]); 185 var assignedDemand = model.Sum(model.Range(0, c), demandSelector); 186 model.Constraint(assignedDemand <= data.Capacities[l]); 187 188 var installCostSelector = model.Function(i => installCostsArray[x[l][i], l]); 189 var installCosts = model.Sum(model.Range(0, c), installCostSelector); 190 obj.AddOperand(installCosts); 191 192 // Flow to other equipments 193 for (int k = 0; k < data.Capacities.Length; k++) { 194 var kc = model.Count(x[k]); 195 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))); 196 obj.AddOperand(model.Sum(model.Range(0, kc), flowCostSelector)); 203 197 } 204 obj.AddOperand(installCostsArray[f1, equipmentsOnLocations[f1]]); 205 } 206 207 model.Minimize(obj); 198 } 199 200 model.Minimize(this.obj); 208 201 209 202 try { … … 218 211 localSolver.Solve(); 219 212 220 var curObj = obj.GetDoubleValue();213 var curObj = this.obj.GetDoubleValue(); 221 214 if (curObj < prevObj) 222 215 UpdateSolution(curObj);
Note: See TracChangeset
for help on using the changeset viewer.