1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022017 Heuristic and Evolutionary Algorithms Laboratory (HEAL)


4  *


5  * This file is part of HeuristicLab.


6  *


7  * HeuristicLab is free software: you can redistribute it and/or modify


8  * it under the terms of the GNU General Public License as published by


9  * the Free Software Foundation, either version 3 of the License, or


10  * (at your option) any later version.


11  *


12  * HeuristicLab is distributed in the hope that it will be useful,


13  * but WITHOUT ANY WARRANTY; without even the implied warranty of


14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the


15  * GNU General Public License for more details.


16  *


17  * You should have received a copy of the GNU General Public License


18  * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.


19  */


20  #endregion


21 


22  using System;


23  using System.Threading;


24  using HeuristicLab.Common;


25  using HeuristicLab.Core;


26  using HeuristicLab.Data;


27  using HeuristicLab.Encodings.IntegerVectorEncoding;


28  using HeuristicLab.Optimization;


29  using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;


30  using localsolver;


31 


32  namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment.Algorithms.LocalSolverNet {


33  [Item("LocalSolver Binary (GQAP)", "LocalSolver algorithm solving the GQAP using 01 decision variables")]


34  [StorableClass]


35  [Creatable(CreatableAttribute.Categories.Algorithms)]


36  public sealed class GQAPBinarySolver : ContextAlgorithm<LocalSolverContext, IntegerVectorEncoding> {


37  public override bool SupportsPause {


38  get { return false; }


39  }


40 


41  public override Type ProblemType {


42  get { return typeof(GQAP); }


43  }


44 


45  public new GQAP Problem {


46  get { return (GQAP)base.Problem; }


47  set { base.Problem = value; }


48  }


49 


50  // LS Program variables


51  private LSExpression[][] x;


52  private LSExpression[] equipmentsOnLocations;


53  private LSExpression obj;


54  private LocalSolver localSolver;


55 


56 


57  [StorableConstructor]


58  private GQAPBinarySolver(bool deserializing) : base(deserializing) { }


59  private GQAPBinarySolver(GQAPBinarySolver original, Cloner cloner)


60  : base(original, cloner) {


61  }


62  public GQAPBinarySolver() {


63  }


64 


65  public override IDeepCloneable Clone(Cloner cloner) {


66  return new GQAPBinarySolver(this, cloner);


67  }


68 


69  private double prevObj;


70  private DateTime lastUpdate;


71  private CancellationToken token;


72 


73  private void LocalSolverOnIterationTicked(LocalSolver ls, LSCallbackType type) {


74  IResult result;


75  Context.Iterations++;


76  if ((DateTime.UtcNow  lastUpdate) > TimeSpan.FromSeconds(1)) {


77  if (Results.TryGetValue("Iterations", out result))


78  ((IntValue)result.Value).Value = Context.Iterations;


79  else Results.Add(new Result("Iterations", new IntValue(Context.Iterations)));


80  lastUpdate = DateTime.UtcNow;


81  }


82 


83  if (token.IsCancellationRequested) localSolver.Stop();


84 


85  var curObj = obj.GetDoubleValue();


86 


87  if (curObj >= prevObj) return;


88  prevObj = curObj;


89  Context.BestQuality = curObj;


90 


91  if (Results.TryGetValue("BestQuality", out result))


92  ((DoubleValue)result.Value).Value = Context.BestQuality;


93  else Results.Add(new Result("BestQuality", new DoubleValue(Context.BestQuality)));


94 


95  var locations = Problem.ProblemInstance.Capacities.Length;


96  var best = new int[Problem.ProblemInstance.Demands.Length];


97  for (var i = 0; i < best.Length; i++) {


98  for (var j = 0; j < locations; j++) {


99  if (x[i][j].GetIntValue() == 1) {


100  best[i] = j;


101  break;


102  }


103  }


104  }


105  var bestVec = new IntegerVector(best);


106  var eval = Problem.ProblemInstance.Evaluate(bestVec);


107  Context.BestSolution = new GQAPSolution(bestVec, eval);


108 


109  var scope = Context.ToScope(new GQAPSolution(new IntegerVector(best), (Evaluation)eval.Clone()), Problem.ProblemInstance.ToSingleObjective(eval));


110  Context.ReplaceIncumbent(scope);


111 


112  if (Results.TryGetValue("BestSolution", out result))


113  result.Value = Context.BestSolution;


114  else Results.Add(new Result("BestSolution", Context.BestSolution));


115 


116  Context.RunOperator(Analyzer, CancellationToken.None);


117  }


118 


119  protected override void Initialize(CancellationToken cancellationToken) {


120  base.Initialize(cancellationToken);


121 


122  prevObj = double.MaxValue;


123  }


124 


125  protected override void Run(CancellationToken cancellationToken) {


126  token = cancellationToken;


127  lastUpdate = DateTime.UtcNow.AddSeconds(1);


128  localSolver = new LocalSolver();


129 


130  // Declares the optimization model


131  LSModel model = localSolver.GetModel();


132 


133  var data = Problem.ProblemInstance;


134 


135  // x[f,l] = 1 if equipments f is on location l, 0 otherwise


136  x = new LSExpression[data.Demands.Length][];


137  for (int f = 0; f < data.Demands.Length; f++) {


138  x[f] = new LSExpression[data.Capacities.Length];


139  for (int l = 0; l < data.Capacities.Length; l++) {


140  x[f][l] = model.Bool();


141  }


142  }


143 


144  // All equipments are installed in exactly 1 location


145  for (int f = 0; f < data.Demands.Length; f++) {


146  LSExpression nbLocationsAssigned = model.Sum();


147  for (int l = 0; l < data.Capacities.Length; l++) {


148  nbLocationsAssigned.AddOperand(x[f][l]);


149  }


150  model.Constraint(nbLocationsAssigned == 1);


151  }


152 


153  // All locations contain not more equipments than there is capacity for


154  for (int l = 0; l < data.Capacities.Length; l++) {


155  LSExpression assignedDemand = model.Sum();


156  for (int f = 0; f < data.Demands.Length; f++) {


157  assignedDemand.AddOperand(x[f][l] * data.Demands[f]);


158  }


159  model.Constraint(assignedDemand <= data.Capacities[l]);


160  }


161 


162  // Index of the assigned location of equipment f


163  equipmentsOnLocations = new LSExpression[data.Demands.Length];


164  for (int f = 0; f < data.Demands.Length; f++) {


165  equipmentsOnLocations[f] = model.Sum();


166  for (int l = 0; l < data.Capacities.Length; l++) {


167  equipmentsOnLocations[f].AddOperand(l * x[f][l]);


168  }


169  }


170 


171  // Create distances as an array to be accessed by an at operator


172  var distancesJagged = new double[data.Capacities.Length][];


173  for (var i = 0; i < data.Capacities.Length; i++) {


174  distancesJagged[i] = new double[data.Capacities.Length];


175  for (var j = 0; j < data.Capacities.Length; j++)


176  distancesJagged[i][j] = data.Distances[i, j];


177  }


178  var installJagged = new double[data.Demands.Length][];


179  for (var i = 0; i < data.Demands.Length; i++) {


180  installJagged[i] = new double[data.Capacities.Length];


181  for (var j = 0; j < data.Capacities.Length; j++)


182  installJagged[i][j] = data.InstallationCosts[i, j];


183  }


184  LSExpression distancesArray = model.Array(distancesJagged);


185  LSExpression installCostsArray = model.Array(installJagged);


186 


187  // Minimize the sum of product distance*flow


188  obj = model.Sum();


189  for (int f1 = 0; f1 < data.Demands.Length; f1++) {


190  for (int f2 = 0; f2 < data.Demands.Length; f2++) {


191  obj.AddOperand(data.TransportationCosts * data.Weights[f1, f2] * distancesArray[equipmentsOnLocations[f1], equipmentsOnLocations[f2]]);


192  }


193  obj.AddOperand(installCostsArray[f1, equipmentsOnLocations[f1]]);


194  }


195 


196  model.Minimize(obj);


197 


198  model.Close();


199 


200  // Parameterizes the solver.


201  LSPhase phase = localSolver.CreatePhase();


202  phase.SetTimeLimit((int)Math.Ceiling(MaximumRuntime.TotalSeconds));


203 


204  localSolver.AddCallback(LSCallbackType.IterationTicked, LocalSolverOnIterationTicked);


205 


206  localSolver.Solve();


207 


208  localSolver.RemoveCallback(LSCallbackType.IterationTicked, LocalSolverOnIterationTicked);


209  localSolver.Dispose();


210  }


211  }


212  }

