source: branches/2457_ExpertSystem/HeuristicLab.Problems.Instances.QAPLIB/3.3/OneSizeInstanceProvider.cs @ 18242

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
using HeuristicLab.Common;

namespace HeuristicLab.Problems.Instances.QAPLIB {
  public class OneSize10InstanceProvider : OneSizeInstanceProvider {
    public OneSize10InstanceProvider() : base(10) { }
  }
  public class OneSize25InstanceProvider : OneSizeInstanceProvider {
    public OneSize25InstanceProvider() : base(25) { }
  }
  public class OneSize50InstanceProvider : OneSizeInstanceProvider {
    public OneSize50InstanceProvider() : base(50) { }
  }
  public class OneSize100InstanceProvider : OneSizeInstanceProvider {
    public OneSize100InstanceProvider() : base(100) { }
  }

  public class OneSizeInstanceProvider : ProblemInstanceProvider<QAPData> {
    public override string Name { get { return "One Size (n = " + Dimension + ")"; } }
    public override string Description { get { return "Instances from various libraries reduced to a dimension of " + Dimension + "."; } }
    public override Uri WebLink { get { return null; } }
    public override string ReferencePublication {
      get {
        return
@"A. Beham, E. Pitzer, S. Wagner, M. Affenzeller. 2017.
Integrating Exploratory Landscape Analysis into Metaheuristic Algorithms.
Lecture Notes in Computer Science 10671, Las Palmas de Gran Canaria, Spanien, pp. 473-480";
      }
    }

    public int Dimension { get; private set; }

    public OneSizeInstanceProvider(int dimension) {
      Dimension = dimension;
    }

    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
      var drezner = new DreznerQAPInstanceProvider();
      foreach (var desc in drezner.GetDataDescriptors()) {
        var dim = int.Parse(Regex.Match(desc.Name, "dre(?<g>\\d+)").Groups["g"].Value);
        if (dim < Dimension) continue;
        yield return new OneSizeDataDescriptor(desc.Name + (dim == Dimension ? "" : "-" + Dimension), desc.Description, drezner, desc);
      }
      // Microarray instances are all greater than 25 dimensions
      var microarray = new MicroarrayQAPInstanceProvider();
      foreach (var desc in microarray.GetDataDescriptors()) {
        var instance = microarray.LoadData(desc);
        if (instance.Dimension < Dimension) continue;
        yield return new OneSizeDataDescriptor(desc.Name + (instance.Dimension == Dimension ? "" : "-" + Dimension), desc.Description, microarray, desc);
      }
      var qaplib = new QAPLIBInstanceProvider();
      foreach (var desc in qaplib.GetDataDescriptors()) {
        var instance = qaplib.LoadData(desc);
        if (instance.Dimension < Dimension) continue;
        yield return new OneSizeDataDescriptor(desc.Name + (instance.Dimension == Dimension ? "" : "-" + Dimension), desc.Description, qaplib, desc);
      }
      // Taillard's instances are basically from the same distribution
      // to avoid over-representation in the set only the tai27e are taken and reduced to 25 dimension
      var taillard = new TaillardQAPInstanceProvider();
      var count = 0;
      foreach (var desc in taillard.GetDataDescriptors().OrderBy(x => x.Name, new NaturalStringComparer())) {
        var dim = int.Parse(Regex.Match(desc.Name, "tai(?<g>\\d+)e").Groups["g"].Value);
        if (dim < Dimension) continue;
        yield return new OneSizeDataDescriptor(desc.Name + (dim == Dimension ? "" : "-" + Dimension), desc.Description, taillard, desc);
        if (++count == 10) break;
      }
    }

    public override QAPData LoadData(IDataDescriptor descriptor) {
      var desc = (OneSizeDataDescriptor)descriptor;
      var data = desc.ActualProvider.LoadData(desc.ActualDescriptor);

      if (data.Dimension <= Dimension) {
        return data;
      }
      var rand = new Random(data.Dimension);

      var tmp = Enumerable.Range(0, data.Dimension).ToArray();
      Shuffle(tmp, rand);
      var throwAway = new bool[data.Dimension];
      foreach (var t in tmp.Take(data.Dimension - Dimension))
        throwAway[t] = true;

      var weights = new double[Dimension, Dimension];
      var distances = new double[Dimension, Dimension];
      var k = 0;
      for (var i = 0; i < data.Dimension; i++) {
        if (throwAway[i]) continue;
        var h = 0;
        for (var j = 0; j < data.Dimension; j++) {
          if (throwAway[j]) continue;
          weights[k, h] = data.Weights[i, j];
          distances[k, h] = data.Distances[i, j];
          h++;
        }
        k++;
      }

      data.Weights = weights;
      data.Distances = distances;
      data.BestKnownAssignment = null;
      data.BestKnownQuality = null;
      data.Dimension = Dimension;
      data.Name += "-" + Dimension;
      data.Description += " (reduced to " + Dimension + " dimensions)";

      return data;
    }
    
    private static void Shuffle(int[] p, Random random) {
      for (var i = p.Length - 1; i > 0; i--) {
        var swapIndex = random.Next(i + 1);
        var h = p[swapIndex];
        p[swapIndex] = p[i];
        p[i] = h;
      }
    }
  }
}