source: branches/PerformanceComparison/HeuristicLab.Problems.Instances.QAPLIB/3.3/OneSizeInstanceProvider.cs @ 14691

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

#2457: working on identification of problem instances

File size: 3.2 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using System.Text;
5using System.Threading.Tasks;
6
7namespace HeuristicLab.Problems.Instances.QAPLIB {
8  public class OneSizeInstanceProvider : ProblemInstanceProvider<QAPData> {
9    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
10      var drezner = new DreznerQAPInstanceProvider();
11      foreach (var desc in drezner.GetDataDescriptors())
12        yield return new OneSizeDataDescriptor(desc.Name + "-25", desc.Description, drezner, desc);
13      var microarray = new MicroarrayQAPInstanceProvider();
14      foreach (var desc in microarray.GetDataDescriptors())
15        yield return new OneSizeDataDescriptor(desc.Name + "-25", desc.Description, microarray, desc);
16      var qaplib = new QAPLIBInstanceProvider();
17      foreach (var desc in qaplib.GetDataDescriptors())
18        yield return new OneSizeDataDescriptor(desc.Name + "-25", desc.Description, qaplib, desc);
19      var taillard = new TaillardQAPInstanceProvider();
20      foreach (var desc in taillard.GetDataDescriptors())
21        yield return new OneSizeDataDescriptor(desc.Name + "-25", desc.Description, taillard, desc);
22    }
23
24    public override QAPData LoadData(IDataDescriptor descriptor) {
25      var desc = (OneSizeDataDescriptor)descriptor;
26      var data = desc.ActualProvider.LoadData(desc.ActualDescriptor);
27      data.BestKnownAssignment = null;
28      data.BestKnownQuality = null;
29      if (data.Dimension <= 25) {
30        return data;
31      }
32      var rand = new Random(data.Dimension);
33
34      var tmp = Enumerable.Range(0, data.Dimension).ToArray();
35      Shuffle(tmp, rand);
36      var throwAway = new bool[data.Dimension];
37      foreach (var t in tmp.Take(data.Dimension - 25))
38        throwAway[t] = true;
39
40      var weights = new double[25, 25];
41      var distances = new double[25, 25];
42      var k = 0;
43      for (var i = 0; i < data.Dimension; i++) {
44        if (throwAway[i]) continue;
45        var h = 0;
46        for (var j = 0; j < data.Dimension; j++) {
47          if (throwAway[j]) continue;
48          weights[k, h] = data.Weights[i, j];
49          distances[k, h] = data.Distances[i, j];
50          h++;
51        }
52        k++;
53      }
54
55      data.Weights = weights;
56      data.Distances = distances;
57      data.BestKnownAssignment = null;
58      data.BestKnownQuality = null;
59      data.Dimension = 25;
60      data.Name += "-25";
61      data.Description += " (reduced or enlarged to 25 dimensions)";
62
63      return data;
64    }
65
66    public override string Name { get { return "One Size"; } }
67    public override string Description { get { return string.Empty; } }
68    public override Uri WebLink { get { return null; } }
69    public override string ReferencePublication { get { return string.Empty; } }
70
71    // permutation must be strictly different in every position
72    private static void Shuffle(int[] p, Random random) {
73      for (var i = p.Length - 1; i > 0; i--) {
74        // Swap element "i" with a random earlier element (excluding itself)
75        var swapIndex = random.Next(i + 1);
76        var h = p[swapIndex];
77        p[swapIndex] = p[i];
78        p[i] = h;
79      }
80    }
81  }
82}
Note: See TracBrowser for help on using the repository browser.