1  using System;


2  using System.Collections.Generic;


3  using System.IO;


4  using System.Linq;


5  using System.Text;


6  using HeuristicLab.Problems.Instances.QAPLIB;


7 


8  namespace BenchmarkDataGenerator {


9  class Program {


10  static void Main(string[] args) {


11  var qaplib = new QAPLIBInstanceProvider();


12  foreach (var desc in qaplib.GetDataDescriptors()) {


13  var qap = qaplib.LoadData(desc);


14  if (qap.Dimension < 20) continue;


15 


16  var swap = UpperToStream(qap.Distances).Any(x => x == 0)


17  && !UpperToStream(qap.Weights).Any(x => x == 0);


18 


19  var weights = qap.Weights;


20  var distances = qap.Distances;


21  if (swap) {


22  weights = qap.Distances;


23  distances = qap.Weights;


24  }


25 


26 


27  alglib.clusterizerstate s;


28  alglib.ahcreport rep;


29 


30 


31  alglib.clusterizercreate(out s);


32  alglib.clusterizersetdistances(s, distances, true);


33  alglib.clusterizerrunahc(s, out rep);


34 


35  var rcount = 0;


36  foreach (var r in new[] { qap.Dimension / 6.0, qap.Dimension / 3.0, qap.Dimension / 1.5 }) {


37  rcount++;


38  var k = (int)Math.Round(r);


39 


40  int[] cidx;


41  int[] cz;


42 


43  alglib.clusterizergetkclusters(rep, k, out cidx, out cz);


44  var clusters = cidx.Select((v, i) => new { Cluster = v, Location = i })


45  .GroupBy(x => x.Cluster).ToDictionary(x => x.Key, x => x.Select(y => y.Location).ToList());


46 


47  var gqapDist = new double[k, k];


48  for (var i = 0; i < k; i++) {


49  var locs = clusters[i];


50  for (var j = i + 1; j < k; j++) {


51  var locs2 = clusters[j];


52 


53  var dist = 0.0;


54  foreach (var u in locs)


55  foreach (var v in locs2)


56  dist += distances[u, v];


57 


58  gqapDist[i, j] = (int)Math.Round(dist / (locs.Count * locs2.Count));


59  gqapDist[j, i] = gqapDist[i, j];


60  }


61  }


62 


63  var avgWeight = ToStream(weights).Average();


64  var avgDistance = ToStream(gqapDist).Average();


65 


66  var sysRand = new Random((qap.Name + k).GetHashCode());


67  var gqapInstall = new double[qap.Dimension, k];


68  for (var i = 0; i < qap.Dimension; i++)


69  for (var j = 0; j < k; j++)


70  gqapInstall[i, j] = sysRand.Next(1, (int)Math.Ceiling(qap.Dimension * avgWeight * avgDistance));


71 


72  var gqapDemands = new double[qap.Dimension];


73  var totalDemand = 0.0;


74 


75  for (var i = 0; i < qap.Dimension; i++) {


76  gqapDemands[i] = sysRand.Next(1, 100);


77  totalDemand += gqapDemands[i];


78  }


79  var minDemand = gqapDemands.Min();


80 


81  foreach (var fac in new[] { 35, 50, 75, 95 }) {


82  var totalCap = (int)Math.Ceiling(100.0 * totalDemand / fac);


83  var gqapCapacities = new double[k];


84 


85  while (true) {


86  var total = 0.0;


87  for (var i = 0; i < k; i++) {


88  gqapCapacities[i] = sysRand.NextDouble();


89  total += gqapCapacities[i];


90  }


91  for (var i = 0; i < k; i++) {


92  gqapCapacities[i] = (int)Math.Round(gqapCapacities[i] / total * totalCap);


93  }


94  var maxCap = gqapCapacities.Max();


95  // locations should be able to accomodate at least one equipment


96  // and one location should not be able to accomodate all equipments


97  // equipments must all fit at least into the biggest location


98  // note: this should lead to mostly feasible instances, but is not a guarantee


99  if (gqapCapacities.All(x => x >= minDemand && x < totalDemand)


100  && gqapDemands.All(x => x <= maxCap)) {


101  break;


102  } else Console.WriteLine("{0}{1}{2}: Another try", qap.Name, k, fac);


103  }


104  var fname = qap.Name + "" + k + "" + fac;


105  Console.Write("Writing {0} ... ", fname);


106  var tc = rcount == 1 ? 4 : (rcount == 2 ? 2 : 1);


107  WriteInstance(fname, qap.Dimension, k, tc, weights, gqapDist, gqapInstall, gqapDemands, gqapCapacities);


108  Console.WriteLine("done.");


109  }


110  }


111  }


112  }


113 


114  private static void WriteInstance(string name, int equipments, int locations, double tc, double[,] weights, double[,] distances, double[,] installCosts, double[] demands, double[] capacities) {


115  using (var writer = File.CreateText(name + ".gqap")) {


116  writer.WriteLine("\t{0}\t{1}\t{2}", equipments, locations, tc);


117  writer.WriteLine(ToString(weights));


118  writer.WriteLine(ToString(distances));


119  writer.WriteLine(ToString(installCosts));


120  writer.WriteLine(string.Join("\t", demands));


121  writer.WriteLine(string.Join("\t", capacities));


122  }


123  }


124 


125  private static IEnumerable<double> ToStream(double[,] mat) {


126  for (var i = mat.GetLowerBound(0); i < mat.GetLowerBound(0) + mat.GetLength(0); i++)


127  for (var j = mat.GetLowerBound(1); j < mat.GetLowerBound(1) + mat.GetLength(1); j++)


128  yield return mat[i, j];


129  }


130 


131  private static IEnumerable<double> UpperToStream(double[,] mat) {


132  var dim = mat.GetLength(0);


133  if (dim != mat.GetLength(1)) throw new InvalidOperationException("matrix is not symmetric");


134 


135  for (var i = 0; i < dim  1; i++)


136  for (var j = i + 1; j < dim; j++)


137  yield return mat[i, j];


138  }


139 


140  private static string ToString(double[,] mat) {


141  var sb = new StringBuilder();


142  for (var i = mat.GetLowerBound(0); i < mat.GetLowerBound(0) + mat.GetLength(0); i++) {


143  if (i > mat.GetLowerBound(0)) sb.AppendLine();


144  for (var j = mat.GetLowerBound(1); j < mat.GetLowerBound(1) + mat.GetLength(1); j++) {


145  sb.Append("\t" + mat[i, j].ToString());


146  }


147  }


148  return sb.ToString();


149  }


150  }


151  }

