1  #region License Information


2  /* HeuristicLab


3  * Copyright (C) 20022012 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.Problems.GeneralizedQuadraticAssignment.Common;


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, DoubleArray demands, DoubleArray capacities, int maximumTries, bool createMostFeasibleSolution, CancellationToken cancelToken) {


61  int tries = 0;


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


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


64  double minViolation = double.MaxValue;


65  Dictionary<int, int> bestAssignment = null;


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


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


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


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


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


71 


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


73  cancelToken.ThrowIfCancellationRequested();


74 


75  assignment.Clear();


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


77  CF.Clear();


78  T.Clear();


79  CL.Clear();


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


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


82 


83  double threshold = 1.0;


84  do {


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


86  int l = L.ChooseUniformRandom(random);


87  L.Remove(l);


88  CL.Add(l);


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


90  }


91  if (T.Any()) {


92  int f = T.ChooseUniformRandom(random);


93  T.Remove(f);


94  F.Remove(f);


95  CF.Add(f);


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


97  assignment.Add(f, l);


98  slack[l] = demands[f];


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


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


101  }


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


103  if (maximumTries > 0) tries++;


104  if (!F.Any()) {


105  bestAssignment = assignment;


106  break;


107  } else if (createMostFeasibleSolution) {


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


109  while (F.Any()) {


110  var f = F.ChooseMax(x => demands[x]);


111  var l = L.ChooseMax(x => slack[x]);


112  F.Remove(f);


113  assignment.Add(f, l);


114  slack[l] = demands[f];


115  }


116  double violation = GQAPEvaluator.EvaluateOverbooking(slack, capacities);


117  if (violation < minViolation) {


118  bestAssignment = assignment;


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


120  minViolation = violation;


121  }


122  }


123  }


124 


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


126 


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


128  }


129 


130  protected override IntegerVector CreateRandomSolution(IRandom random, DoubleArray demands, DoubleArray capacities) {


131  return CreateSolution(random, demands, capacities,


132  MaximumTriesParameter.ActualValue.Value,


133  CreateMostFeasibleSolutionParameter.ActualValue.Value,


134  CancellationToken);


135  }


136 


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


138  foreach (int f in facilities) {


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


140  }


141  }


142 


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


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


145  }


146 


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


148  foreach (int l in locations) {


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


150  }


151  }


152  }


153  }

