[15578] | 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 | }
|
---|
[15713] | 94 | var maxCap = gqapCapacities.Max();
|
---|
[15578] | 95 | // locations should be able to accomodate at least one equipment
|
---|
| 96 | // and one location should not be able to accomodate all equipments
|
---|
[15713] | 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);
|
---|
[15578] | 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 | }
|
---|