[14691] | 1 | using System;
|
---|
| 2 | using System.Collections.Generic;
|
---|
| 3 | using System.Linq;
|
---|
[15031] | 4 | using System.Text.RegularExpressions;
|
---|
[14691] | 5 |
|
---|
| 6 | namespace HeuristicLab.Problems.Instances.QAPLIB {
|
---|
| 7 | public class OneSizeInstanceProvider : ProblemInstanceProvider<QAPData> {
|
---|
| 8 | public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
|
---|
| 9 | var drezner = new DreznerQAPInstanceProvider();
|
---|
[15031] | 10 | foreach (var desc in drezner.GetDataDescriptors()) {
|
---|
| 11 | var dim = int.Parse(Regex.Match(desc.Name, "dre(?<g>\\d+)").Groups["g"].Value);
|
---|
| 12 | if (dim < 25) continue;
|
---|
| 13 | yield return new OneSizeDataDescriptor(desc.Name + (dim == 25 ? "" : "-25"), desc.Description, drezner, desc);
|
---|
| 14 | }
|
---|
| 15 | // Microarray instances are all greater than 25 dimensions
|
---|
[14691] | 16 | var microarray = new MicroarrayQAPInstanceProvider();
|
---|
[15031] | 17 | foreach (var desc in microarray.GetDataDescriptors()) {
|
---|
[14691] | 18 | yield return new OneSizeDataDescriptor(desc.Name + "-25", desc.Description, microarray, desc);
|
---|
[15031] | 19 | }
|
---|
[14691] | 20 | var qaplib = new QAPLIBInstanceProvider();
|
---|
[15031] | 21 | foreach (var desc in qaplib.GetDataDescriptors()) {
|
---|
| 22 | var instance = qaplib.LoadData(desc);
|
---|
| 23 | if (instance.Dimension < 25) continue;
|
---|
| 24 | yield return new OneSizeDataDescriptor(desc.Name + (instance.Dimension == 25 ? "" : "-25"), desc.Description, qaplib, desc);
|
---|
| 25 | }
|
---|
| 26 | // Taillard's instances are basically from the same distribution
|
---|
| 27 | // to avoid over-representation in the set only the tai27e are taken and reduced to 25 dimension
|
---|
[14691] | 28 | var taillard = new TaillardQAPInstanceProvider();
|
---|
[15031] | 29 | foreach (var desc in taillard.GetDataDescriptors()) {
|
---|
| 30 | if (!desc.Name.StartsWith("tai27e")) continue;
|
---|
[14691] | 31 | yield return new OneSizeDataDescriptor(desc.Name + "-25", desc.Description, taillard, desc);
|
---|
[15031] | 32 | }
|
---|
[14691] | 33 | }
|
---|
| 34 |
|
---|
| 35 | public override QAPData LoadData(IDataDescriptor descriptor) {
|
---|
| 36 | var desc = (OneSizeDataDescriptor)descriptor;
|
---|
| 37 | var data = desc.ActualProvider.LoadData(desc.ActualDescriptor);
|
---|
| 38 | data.BestKnownAssignment = null;
|
---|
| 39 | data.BestKnownQuality = null;
|
---|
| 40 | if (data.Dimension <= 25) {
|
---|
| 41 | return data;
|
---|
| 42 | }
|
---|
| 43 | var rand = new Random(data.Dimension);
|
---|
| 44 |
|
---|
| 45 | var tmp = Enumerable.Range(0, data.Dimension).ToArray();
|
---|
| 46 | Shuffle(tmp, rand);
|
---|
| 47 | var throwAway = new bool[data.Dimension];
|
---|
| 48 | foreach (var t in tmp.Take(data.Dimension - 25))
|
---|
| 49 | throwAway[t] = true;
|
---|
| 50 |
|
---|
| 51 | var weights = new double[25, 25];
|
---|
| 52 | var distances = new double[25, 25];
|
---|
| 53 | var k = 0;
|
---|
| 54 | for (var i = 0; i < data.Dimension; i++) {
|
---|
| 55 | if (throwAway[i]) continue;
|
---|
| 56 | var h = 0;
|
---|
| 57 | for (var j = 0; j < data.Dimension; j++) {
|
---|
| 58 | if (throwAway[j]) continue;
|
---|
| 59 | weights[k, h] = data.Weights[i, j];
|
---|
| 60 | distances[k, h] = data.Distances[i, j];
|
---|
| 61 | h++;
|
---|
| 62 | }
|
---|
| 63 | k++;
|
---|
| 64 | }
|
---|
| 65 |
|
---|
| 66 | data.Weights = weights;
|
---|
| 67 | data.Distances = distances;
|
---|
| 68 | data.BestKnownAssignment = null;
|
---|
| 69 | data.BestKnownQuality = null;
|
---|
| 70 | data.Dimension = 25;
|
---|
| 71 | data.Name += "-25";
|
---|
[15031] | 72 | data.Description += " (reduced to 25 dimensions)";
|
---|
[14691] | 73 |
|
---|
| 74 | return data;
|
---|
| 75 | }
|
---|
| 76 |
|
---|
| 77 | public override string Name { get { return "One Size"; } }
|
---|
| 78 | public override string Description { get { return string.Empty; } }
|
---|
| 79 | public override Uri WebLink { get { return null; } }
|
---|
| 80 | public override string ReferencePublication { get { return string.Empty; } }
|
---|
[15031] | 81 |
|
---|
[14691] | 82 | private static void Shuffle(int[] p, Random random) {
|
---|
| 83 | for (var i = p.Length - 1; i > 0; i--) {
|
---|
| 84 | var swapIndex = random.Next(i + 1);
|
---|
| 85 | var h = p[swapIndex];
|
---|
| 86 | p[swapIndex] = p[i];
|
---|
| 87 | p[i] = h;
|
---|
| 88 | }
|
---|
| 89 | }
|
---|
| 90 | }
|
---|
| 91 | }
|
---|