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

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using HeuristicLab.Problems.Instances.QAPLIB;

namespace BenchmarkDataGenerator {
  class Program {
    static void Main(string[] args) {
      var qaplib = new QAPLIBInstanceProvider();
      foreach (var desc in qaplib.GetDataDescriptors()) {
        var qap = qaplib.LoadData(desc);
        if (qap.Dimension < 20) continue;

        var swap = UpperToStream(qap.Distances).Any(x => x == 0)
          && !UpperToStream(qap.Weights).Any(x => x == 0);

        var weights = qap.Weights;
        var distances = qap.Distances;
        if (swap) {
          weights = qap.Distances;
          distances = qap.Weights;
        }
        

        alglib.clusterizerstate s;
        alglib.ahcreport rep;
        

        alglib.clusterizercreate(out s);
        alglib.clusterizersetdistances(s, distances, true);
        alglib.clusterizerrunahc(s, out rep);

        var rcount = 0;
        foreach (var r in new[] { qap.Dimension / 6.0, qap.Dimension / 3.0, qap.Dimension / 1.5 }) {
          rcount++;
          var k = (int)Math.Round(r);

          int[] cidx;
          int[] cz;

          alglib.clusterizergetkclusters(rep, k, out cidx, out cz);
          var clusters = cidx.Select((v, i) => new { Cluster = v, Location = i })
                             .GroupBy(x => x.Cluster).ToDictionary(x => x.Key, x => x.Select(y => y.Location).ToList());

          var gqapDist = new double[k, k];
          for (var i = 0; i < k; i++) {
            var locs = clusters[i];
            for (var j = i + 1; j < k; j++) {
              var locs2 = clusters[j];

              var dist = 0.0;
              foreach (var u in locs)
                foreach (var v in locs2)
                  dist += distances[u, v];

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

          var avgWeight = ToStream(weights).Average();
          var avgDistance = ToStream(gqapDist).Average();

          var sysRand = new Random((qap.Name + k).GetHashCode());
          var gqapInstall = new double[qap.Dimension, k];
          for (var i = 0; i < qap.Dimension; i++)
            for (var j = 0; j < k; j++)
              gqapInstall[i, j] = sysRand.Next(1, (int)Math.Ceiling(qap.Dimension * avgWeight * avgDistance));

          var gqapDemands = new double[qap.Dimension];
          var totalDemand = 0.0;

          for (var i = 0; i < qap.Dimension; i++) {
            gqapDemands[i] = sysRand.Next(1, 100);
            totalDemand += gqapDemands[i];
          }
          var minDemand = gqapDemands.Min();

          foreach (var fac in new[] { 35, 50, 75, 95 }) {
            var totalCap = (int)Math.Ceiling(100.0 * totalDemand / fac);
            var gqapCapacities = new double[k];

            while (true) {
              var total = 0.0;
              for (var i = 0; i < k; i++) {
                gqapCapacities[i] = sysRand.NextDouble();
                total += gqapCapacities[i];
              }
              for (var i = 0; i < k; i++) {
                gqapCapacities[i] = (int)Math.Round(gqapCapacities[i] / total * totalCap);
              }
              // locations should be able to accomodate at least one equipment
              // and one location should not be able to accomodate all equipments
              if (gqapCapacities.All(x => x >= minDemand && x < totalDemand)) break;
              else Console.WriteLine("{0}-{1}-{2}: Another try", qap.Name, k, fac);
            }
            var fname = qap.Name + "-" + k + "-" + fac;
            Console.Write("Writing {0} ... ", fname);
            var tc = rcount == 1 ? 4 : (rcount == 2 ? 2 : 1);
            WriteInstance(fname, qap.Dimension, k, tc, weights, gqapDist, gqapInstall, gqapDemands, gqapCapacities);
            Console.WriteLine("done.");
          }
        }
      }
    }

    private static void WriteInstance(string name, int equipments, int locations, double tc, double[,] weights, double[,] distances, double[,] installCosts, double[] demands, double[] capacities) {
      using (var writer = File.CreateText(name + ".gqap")) {
        writer.WriteLine("\t{0}\t{1}\t{2}", equipments, locations, tc);
        writer.WriteLine(ToString(weights));
        writer.WriteLine(ToString(distances));
        writer.WriteLine(ToString(installCosts));
        writer.WriteLine(string.Join("\t", demands));
        writer.WriteLine(string.Join("\t", capacities));
      }
    }

    private static IEnumerable<double> ToStream(double[,] mat) {
      for (var i = mat.GetLowerBound(0); i < mat.GetLowerBound(0) + mat.GetLength(0); i++)
        for (var j = mat.GetLowerBound(1); j < mat.GetLowerBound(1) + mat.GetLength(1); j++)
          yield return mat[i, j];
    }

    private static IEnumerable<double> UpperToStream(double[,] mat) {
      var dim = mat.GetLength(0);
      if (dim != mat.GetLength(1)) throw new InvalidOperationException("matrix is not symmetric");

      for (var i = 0; i < dim - 1; i++)
        for (var j = i + 1; j < dim; j++)
          yield return mat[i, j];
    }

    private static string ToString(double[,] mat) {
      var sb = new StringBuilder();
      for (var i = mat.GetLowerBound(0); i < mat.GetLowerBound(0) + mat.GetLength(0); i++) {
        if (i > mat.GetLowerBound(0)) sb.AppendLine();
        for (var j = mat.GetLowerBound(1); j < mat.GetLowerBound(1) + mat.GetLength(1); j++) {
          sb.Append("\t" + mat[i, j].ToString());
        }
      }
      return sb.ToString();
    }
  }
}