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;


64  int tries = 0;


65  var assignment = new Dictionary<int, int>(demands.Length);


66  DoubleArray slack = new DoubleArray(capacities.Length);


67  double minViolation = double.MaxValue;


68  Dictionary<int, int> bestAssignment = null;


69  HashSet<int> CF = new HashSet<int>(), // set of chosen facilities / equipments


70  T = new HashSet<int>(), // set of facilities / equpiments that can be assigned to the set of chosen locations (CL)


71  CL = new HashSet<int>(), // set of chosen locations


72  F = new HashSet<int>(Enumerable.Range(0, demands.Length)), // set of (initially) all facilities / equipments


73  L = new HashSet<int>(Enumerable.Range(0, capacities.Length)); // set of (initially) all locations


74 


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


76  cancelToken.ThrowIfCancellationRequested();


77 


78  assignment.Clear();


79  for (int i = 0; i < capacities.Length; i++) slack[i] = capacities[i];


80  CF.Clear();


81  T.Clear();


82  CL.Clear();


83  F.Clear(); F.UnionWith(Enumerable.Range(0, demands.Length));


84  L.Clear(); L.UnionWith(Enumerable.Range(0, capacities.Length));


85 


86  double threshold = 1.0;


87  do {


88  if (L.Any() && random.NextDouble() < threshold) {


89  int l = L.SampleRandom(random);


90  L.Remove(l);


91  CL.Add(l);


92  T = new HashSet<int>(WithDemandEqualOrLess(F, GetMaximumSlack(slack, CL), demands));


93  }


94  if (T.Any()) {


95  int f = T.SampleRandom(random);


96  T.Remove(f);


97  F.Remove(f);


98  CF.Add(f);


99  int l = WithSlackGreaterOrEqual(CL, demands[f], slack).SampleRandom(random);


100  assignment.Add(f, l);


101  slack[l] = demands[f];


102  T = new HashSet<int>(WithDemandEqualOrLess(F, GetMaximumSlack(slack, CL), demands));


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


104  }


105  } while (T.Any()  L.Any());


106  if (maximumTries > 0) tries++;


107  if (!F.Any()) {


108  bestAssignment = assignment;


109  break;


110  } else if (createMostFeasibleSolution) {


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


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


113  CL.Add(l);


114  L.Remove(l);


115  }


116  while (F.Any()) {


117  var f = F.MaxItems(x => demands[x]).SampleRandom(random);


118  var l = CL.MaxItems(x => slack[x]).SampleRandom(random);


119  F.Remove(f);


120  assignment.Add(f, l);


121  slack[l] = demands[f];


122  }


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


124  if (violation < minViolation) {


125  bestAssignment = assignment;


126  assignment = new Dictionary<int, int>(demands.Length);


127  minViolation = violation;


128  }


129  }


130  }


131 


132  if (bestAssignment == null  bestAssignment.Count != demands.Length) throw new InvalidOperationException(String.Format("No solution could be found in {0} tries.", maximumTries));


133 


134  return new IntegerVector(bestAssignment.OrderBy(x => x.Key).Select(x => x.Value).ToArray());


135  }


136 


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


138  return CreateSolution(random, problemInstance,


139  MaximumTriesParameter.ActualValue.Value,


140  CreateMostFeasibleSolutionParameter.ActualValue.Value,


141  CancellationToken);


142  }


143 


144  private static IEnumerable<int> WithDemandEqualOrLess(IEnumerable<int> facilities, double maximum, DoubleArray demands) {


145  foreach (int f in facilities) {


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


147  }


148  }


149 


150  private static double GetMaximumSlack(DoubleArray slack, HashSet<int> CL) {


151  return slack.Select((val, idx) => new { idx, val }).Where(x => CL.Contains(x.idx)).Select(x => x.val).Max();


152  }


153 


154  private static IEnumerable<int> WithSlackGreaterOrEqual(HashSet<int> locations, double minimum, DoubleArray slack) {


155  foreach (int l in locations) {


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


157  }


158  }


159  }


160  }

