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.Collections.Generic;


24  using System.Linq;


25  using System.Threading;


26  using HeuristicLab.Common;


27  using HeuristicLab.Core;


28  using HeuristicLab.Data;


29  using HeuristicLab.Encodings.IntegerVectorEncoding;


30  using HeuristicLab.Parameters;


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


32  using HeuristicLab.Random;


33 


34  namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {


35  [Item("GreedyRandomizedSolutionCreator", "Creates a solution according to the procedure described in Mateus, G., Resende, M., and Silva, R. 2011. GRASP with pathrelinking for the generalized quadratic assignment problem. Journal of Heuristics 17, Springer Netherlands, pp. 527565.")]


36  [StorableClass]


37  public class GreedyRandomizedSolutionCreator : GQAPStochasticSolutionCreator {


38 


39  public IValueLookupParameter<IntValue> MaximumTriesParameter {


40  get { return (IValueLookupParameter<IntValue>)Parameters["MaximumTries"]; }


41  }


42  public IValueLookupParameter<BoolValue> CreateMostFeasibleSolutionParameter {


43  get { return (IValueLookupParameter<BoolValue>)Parameters["CreateMostFeasibleSolution"]; }


44  }


45 


46  [StorableConstructor]


47  protected GreedyRandomizedSolutionCreator(bool deserializing) : base(deserializing) { }


48  protected GreedyRandomizedSolutionCreator(GreedyRandomizedSolutionCreator original, Cloner cloner)


49  : base(original, cloner) { }


50  public GreedyRandomizedSolutionCreator()


51  : base() {


52  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)));


53  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)));


54  }


55 


56  public override IDeepCloneable Clone(Cloner cloner) {


57  return new GreedyRandomizedSolutionCreator(this, cloner);


58  }


59 


60  public static IntegerVector CreateSolution(IRandom random, GQAPInstance problemInstance,


61  int maximumTries, bool createMostFeasibleSolution, CancellationToken cancelToken) {


62  var demands = problemInstance.Demands;


63  var capacities = problemInstance.Capacities.ToArray();


64  var equipments = demands.Length;


65  var locations = capacities.Length;


66  int tries = 0;


67  var assignment = new int[equipments];


68  var slack = new double[locations];


69  double minViolation = double.MaxValue;


70  int[] bestAssignment = null;


71  var CF = new bool[equipments]; // set of chosen facilities / equipments


72  var T = new List<int>(equipments); // set of facilities / equpiments that can be assigned to the set of chosen locations (CL)


73  var CL_list = new List<int>(locations); // list of chosen locations


74  var CL_selected = new bool[locations]; // bool decision if location is chosen


75  var F = new List<int>(equipments); // set of (initially) all facilities / equipments


76  var L = new List<int>(locations); // set of (initially) all locations


77 


78  while (maximumTries <= 0  tries < maximumTries) {


79  cancelToken.ThrowIfCancellationRequested();


80 


81  Array.Copy(capacities, slack, locations);


82  Array.Clear(CF, 0, equipments);


83  Array.Clear(CL_selected, 0, locations);


84  CL_list.Clear();


85  T.Clear();


86 


87  F.Clear(); F.AddRange(Enumerable.Range(0, equipments));


88  L.Clear(); L.AddRange(Enumerable.Range(0, locations));


89 


90  double threshold = 1.0;


91  do {


92  if (L.Count > 0 && random.NextDouble() < threshold) {


93  int l = L.SampleRandom(random);


94  L.Remove(l);


95  CL_list.Add(l);


96  CL_selected[l] = true;


97  T = new List<int>(WhereDemandEqualOrLess(F, GetMaximumSlack(slack, CL_selected), demands));


98  }


99  if (T.Count > 0) {


100  var fidx = Enumerable.Range(0, T.Count).SampleRandom(random);


101  var f = T[fidx];


102  T.RemoveAt(fidx);


103  F.Remove(f); // TODO: slow


104  CF[f] = true;


105  int l = WhereSlackGreaterOrEqual(CL_list, demands[f], slack).SampleRandom(random);


106  assignment[f] = l + 1;


107  slack[l] = demands[f];


108  T = new List<int>(WhereDemandEqualOrLess(F, GetMaximumSlack(slack, CL_selected), demands));


109  threshold = 1.0  (double)T.Count / Math.Max(F.Count, 1.0);


110  }


111  } while (T.Count > 0  L.Count > 0);


112  if (maximumTries > 0) tries++;


113  if (F.Count == 0) {


114  bestAssignment = assignment;


115  break;


116  } else if (createMostFeasibleSolution) {


117  // complete the solution and remember the one with least violation


118  foreach (var l in L.ToArray()) {


119  CL_list.Add(l);


120  CL_selected[l] = true;


121  L.Remove(l);


122  }


123  while (F.Count > 0) {


124  var f = F.Select((v, i) => new { Index = i, Value = v }).MaxItems(x => demands[x.Value]).SampleRandom(random);


125  var l = CL_list.MaxItems(x => slack[x]).SampleRandom(random);


126  F.RemoveAt(f.Index);


127  assignment[f.Value] = l + 1;


128  slack[l] = demands[f.Value];


129  }


130  double violation = slack.Select(x => x < 0 ? x : 0).Sum();


131  if (violation < minViolation) {


132  bestAssignment = assignment;


133  assignment = new int[equipments];


134  minViolation = violation;


135  }


136  }


137  }


138 


139  if (bestAssignment == null  bestAssignment.Any(x => x == 0))


140  throw new InvalidOperationException(String.Format("No solution could be found in {0} tries.", maximumTries));


141 


142  return new IntegerVector(bestAssignment.Select(x => x  1).ToArray());


143  }


144 


145  protected override IntegerVector CreateRandomSolution(IRandom random, GQAPInstance problemInstance) {


146  return CreateSolution(random, problemInstance,


147  MaximumTriesParameter.ActualValue.Value,


148  CreateMostFeasibleSolutionParameter.ActualValue.Value,


149  CancellationToken);


150  }


151 


152  private static IEnumerable<int> WhereDemandEqualOrLess(IEnumerable<int> facilities, double maximum, DoubleArray demands) {


153  foreach (int f in facilities) {


154  if (demands[f] <= maximum) yield return f;


155  }


156  }


157 


158  private static double GetMaximumSlack(double[] slack, bool[] CL) {


159  var max = double.MinValue;


160  for (var i = 0; i < slack.Length; i++) {


161  if (CL[i] && max < slack[i]) max = slack[i];


162  }


163  return max;


164  }


165 


166  private static IEnumerable<int> WhereSlackGreaterOrEqual(IEnumerable<int> locations, double minimum, double[] slack) {


167  foreach (int l in locations) {


168  if (slack[l] >= minimum) yield return l;


169  }


170  }


171  }


172  }

