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.Linq;


24  using System.Threading;


25  using HeuristicLab.Analysis;


26  using HeuristicLab.Common;


27  using HeuristicLab.Core;


28  using HeuristicLab.Data;


29  using HeuristicLab.Encodings.IntegerVectorEncoding;


30  using HeuristicLab.Optimization;


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


32  using localsolver;


33 


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


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


36  [StorableClass]


37  [Creatable(CreatableAttribute.Categories.Algorithms)]


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


39  public override bool SupportsPause {


40  get { return false; }


41  }


42 


43  public override Type ProblemType {


44  get { return typeof(GQAP); }


45  }


46 


47  public new GQAP Problem {


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


49  set { base.Problem = value; }


50  }


51 


52  // LS Program variables


53  private LSExpression[][] x;


54  private LSExpression[] equipmentsOnLocations;


55  private LSExpression obj;


56  private LocalSolver localSolver;


57 


58 


59  [StorableConstructor]


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


61  private GQAPBinarySolver(GQAPBinarySolver original, Cloner cloner)


62  : base(original, cloner) {


63  }


64  public GQAPBinarySolver() {


65  }


66 


67  public override IDeepCloneable Clone(Cloner cloner) {


68  return new GQAPBinarySolver(this, cloner);


69  }


70 


71  private double prevObj;


72  private DateTime lastUpdate;


73  private CancellationToken token;


74 


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


76  IResult result;


77  Context.Iterations++;


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


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


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


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


82  lastUpdate = DateTime.UtcNow;


83  }


84 


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


86 


87  var curObj = obj.GetDoubleValue();


88 


89  if (curObj >= prevObj) return;


90  prevObj = curObj;


91  Context.BestQuality = curObj;


92 


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


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


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


96 


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


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


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


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


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


102  best[i] = j;


103  break;


104  }


105  }


106  }


107  var bestVec = new IntegerVector(best);


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


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


110 


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


112  Context.ReplaceIncumbent(scope);


113 


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


115  result.Value = Context.BestSolution;


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


117 


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


119  }


120 


121  protected override void Initialize(CancellationToken cancellationToken) {


122  base.Initialize(cancellationToken);


123 


124  prevObj = double.MaxValue;


125  }


126 


127  protected override void Run(CancellationToken cancellationToken) {


128  var qpc = ((MultiAnalyzer)Analyzer).Operators.OfType<QualityPerClockAnalyzer>().FirstOrDefault();


129  if (qpc != null) {


130  qpc.LastUpdateTimeParameter.ActualName = Context.LastUpdateTimeParameter.Name;


131  }


132  token = cancellationToken;


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


134  localSolver = new LocalSolver();


135 


136  // Declares the optimization model


137  LSModel model = localSolver.GetModel();


138 


139  var data = Problem.ProblemInstance;


140 


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


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


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


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


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


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


147  }


148  }


149 


150  // All equipments are installed in exactly 1 location


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


152  LSExpression nbLocationsAssigned = model.Sum();


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


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


155  }


156  model.Constraint(nbLocationsAssigned == 1);


157  }


158 


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


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


161  LSExpression assignedDemand = model.Sum();


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


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


164  }


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


166  }


167 


168  // Index of the assigned location of equipment f


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


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


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


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


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


174  }


175  }


176 


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


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


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


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


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


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


183  }


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


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


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


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


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


189  }


190  LSExpression distancesArray = model.Array(distancesJagged);


191  LSExpression installCostsArray = model.Array(installJagged);


192 


193  // Minimize the sum of product distance*flow


194  obj = model.Sum();


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


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


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


198  }


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


200  }


201 


202  model.Minimize(obj);


203 


204  try {


205  model.Close();


206 


207  // Parameterizes the solver.


208  LSPhase phase = localSolver.CreatePhase();


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


210 


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


212 


213  Context.LastUpdateTimeParameter.Value = new DateTimeValue(DateTime.UtcNow);


214 


215  localSolver.Solve();


216 


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


218  } finally {


219  localSolver.Dispose();


220  }


221 


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


223  }


224  }


225  }

