source: branches/GeneralizedQAP/BenchmarkDataGenerator/Program.cs @ 15578

Last change on this file since 15578 was 15578, checked in by abeham, 5 years ago

#1614: Added program to generate new benchmark instances based on QAPLIB (same flow matrices, clustered distance matrices and randomly chosen installation costs, demands, and capacities)

File size: 5.6 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.IO;
4using System.Linq;
5using System.Text;
6using HeuristicLab.Problems.Instances.QAPLIB;
7
8namespace 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              // locations should be able to accomodate at least one equipment
95              // and one location should not be able to accomodate all equipments
96              if (gqapCapacities.All(x => x >= minDemand && x < totalDemand)) break;
97              else Console.WriteLine("{0}-{1}-{2}: Another try", qap.Name, k, fac);
98            }
99            var fname = qap.Name + "-" + k + "-" + fac;
100            Console.Write("Writing {0} ... ", fname);
101            var tc = rcount == 1 ? 4 : (rcount == 2 ? 2 : 1);
102            WriteInstance(fname, qap.Dimension, k, tc, weights, gqapDist, gqapInstall, gqapDemands, gqapCapacities);
103            Console.WriteLine("done.");
104          }
105        }
106      }
107    }
108
109    private static void WriteInstance(string name, int equipments, int locations, double tc, double[,] weights, double[,] distances, double[,] installCosts, double[] demands, double[] capacities) {
110      using (var writer = File.CreateText(name + ".gqap")) {
111        writer.WriteLine("\t{0}\t{1}\t{2}", equipments, locations, tc);
112        writer.WriteLine(ToString(weights));
113        writer.WriteLine(ToString(distances));
114        writer.WriteLine(ToString(installCosts));
115        writer.WriteLine(string.Join("\t", demands));
116        writer.WriteLine(string.Join("\t", capacities));
117      }
118    }
119
120    private static IEnumerable<double> ToStream(double[,] mat) {
121      for (var i = mat.GetLowerBound(0); i < mat.GetLowerBound(0) + mat.GetLength(0); i++)
122        for (var j = mat.GetLowerBound(1); j < mat.GetLowerBound(1) + mat.GetLength(1); j++)
123          yield return mat[i, j];
124    }
125
126    private static IEnumerable<double> UpperToStream(double[,] mat) {
127      var dim = mat.GetLength(0);
128      if (dim != mat.GetLength(1)) throw new InvalidOperationException("matrix is not symmetric");
129
130      for (var i = 0; i < dim - 1; i++)
131        for (var j = i + 1; j < dim; j++)
132          yield return mat[i, j];
133    }
134
135    private static string ToString(double[,] mat) {
136      var sb = new StringBuilder();
137      for (var i = mat.GetLowerBound(0); i < mat.GetLowerBound(0) + mat.GetLength(0); i++) {
138        if (i > mat.GetLowerBound(0)) sb.AppendLine();
139        for (var j = mat.GetLowerBound(1); j < mat.GetLowerBound(1) + mat.GetLength(1); j++) {
140          sb.Append("\t" + mat[i, j].ToString());
141        }
142      }
143      return sb.ToString();
144    }
145  }
146}
Note: See TracBrowser for help on using the repository browser.