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 | }
|
---|