source: branches/1614_GeneralizedQAP/BenchmarkDataGenerator/Program.cs @ 15713

Last change on this file since 15713 was 15713, checked in by abeham, 4 years ago

#1614:

  • added additional constraint to benchmark data generator and updated one instance that was affected by this
  • added fitness landscape characteristics for the GQAP
  • fixed RLD analysis view to compensate for empty convergence graphs
  • fixed CPLEX solvers not using the obj value when the solver terminates (callback is not called if proven optimal solution is found)
  • added code for local solver to also check on final quality
File size: 5.9 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              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}
Note: See TracBrowser for help on using the repository browser.