source: trunk/sources/HeuristicLab.Problems.Instances.QAPLIB/3.3/QAPLIBInstanceProvider.cs @ 8910

Last change on this file since 8910 was 8910, checked in by abeham, 9 years ago

#1841:

  • Corrected best known solutions in new taillard and microarray instances
  • Improved computation of an average fitness in the QAP
File size: 9.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2012 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using System.IO;
25using System.Linq;
26using System.Reflection;
27using System.Text.RegularExpressions;
28using ICSharpCode.SharpZipLib.Zip;
29
30namespace HeuristicLab.Problems.Instances.QAPLIB {
31  public class QAPLIBInstanceProvider : ProblemInstanceProvider<QAPData> {
32    #region Reversed instances
33    // These instances specified their best known solution in the wrong order
34    protected virtual HashSet<string> ReversedSolutions {
35      get {
36            return new HashSet<string>(new string[] {
37              "bur26a",
38              "bur26b",
39              "bur26c",
40              "bur26d",
41              "bur26e",
42              "bur26f",
43              "bur26g",
44              "bur26h",
45              "chr12a",
46              "chr12b",
47              "chr12c",
48              "chr15a",
49              "chr15b",
50              "chr15c",
51              "chr18a",
52              "chr18b",
53              "chr20a",
54              "chr20b",
55              "chr20c",
56              "chr22a",
57              "chr22b",
58              "chr25a",
59              "esc16a",
60              "esc16b",
61              "esc16c",
62              "esc16d",
63              "esc16e",
64              "esc16g",
65              "esc16h",
66              "esc16i",
67              "esc16j",
68              "esc32a",
69              "esc32b",
70              "esc32c",
71              "esc32d",
72              "esc32e",
73              "esc32f",
74              "esc32g",
75              "esc32h",
76              "had12",
77              "had14",
78              "had16",
79              "had18",
80              "had20",
81              "kra32",
82              "lipa20a",
83              "lipa30a",
84              "lipa40a",
85              "lipa50a",
86              "lipa60a",
87              "lipa70a",
88              "lipa80a",
89              "lipa90a",
90              "nug12",
91              "nug14",
92              "nug15",
93              "nug16a",
94              "nug16b",
95              "nug17",
96              "nug18",
97              "nug20",
98              "nug21",
99              "nug22",
100              "nug24",
101              "nug25",
102              "nug27",
103              "nug28",
104              "rou12",
105              "rou15",
106              "rou20",
107              "scr12",
108              "scr15",
109              "scr20",
110              "sko100a",
111              "sko100b",
112              "sko100c",
113              "sko100d",
114              "sko100e",
115              "sko100f",
116              "sko49",
117              "sko81",
118              "sko90",
119              "ste36a",
120              "ste36b",
121              "tai100a",
122              "tai100b",
123              "tai12a",
124              "tai12b",
125              "tai150b",
126              "tai15a",
127              "tai15b",
128              "tai17a",
129              "tai20a",
130              "tai20b",
131              "tai256c",
132              "tai25a",
133              "tai25b",
134              "tai30a",
135              "tai30b",
136              "tai35a",
137              "tai35b",
138              "tai40a",
139              "tai40b",
140              "tai50a",
141              "tai50b",
142              "tai60a",
143              "tai60b",
144              "tai64c",
145              "tai80a",
146              "tai80b",
147              "wil100"
148        });
149      }
150    }
151    #endregion
152
153    public override string Name {
154      get { return "QAPLIB"; }
155    }
156
157    public override string Description {
158      get { return "Quadratic Assignment Problem Library"; }
159    }
160
161    public override Uri WebLink {
162      get { return new Uri("http://www.seas.upenn.edu/qaplib/"); }
163    }
164
165    public override string ReferencePublication {
166      get {
167        return @"R. E. Burkard, S. E. Karisch, and F. Rendl. 1997.
168QAPLIB - A Quadratic Assignment Problem Library.
169Journal of Global Optimization, 10, pp. 391-403.";
170      }
171    }
172
173    protected virtual string FileName { get { return "qap"; } }
174
175    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
176      Dictionary<string, string> solutions = new Dictionary<string, string>();
177      var solutionsArchiveName = GetResourceName(FileName + @"\.sln\.zip");
178      if (!String.IsNullOrEmpty(solutionsArchiveName)) {
179        using (var solutionsZipFile = new ZipInputStream(GetType().Assembly.GetManifestResourceStream(solutionsArchiveName))) {
180          foreach (var entry in GetZipContents(solutionsZipFile))
181            solutions.Add(Path.GetFileNameWithoutExtension(entry) + ".dat", entry);
182        }
183      }
184      var instanceArchiveName = GetResourceName(FileName + @"\.dat\.zip");
185      if (String.IsNullOrEmpty(instanceArchiveName)) yield break;
186
187      using (var instanceStream = new ZipInputStream(GetType().Assembly.GetManifestResourceStream(instanceArchiveName))) {
188        foreach (var entry in GetZipContents(instanceStream).OrderBy(x => x)) {
189          yield return new QAPLIBDataDescriptor(Path.GetFileNameWithoutExtension(entry), GetDescription(), entry, solutions.ContainsKey(entry) ? solutions[entry] : String.Empty);
190        }
191      }
192    }
193
194    public override QAPData LoadData(IDataDescriptor id) {
195      var descriptor = (QAPLIBDataDescriptor)id;
196      var instanceArchiveName = GetResourceName(FileName + @"\.dat\.zip");
197      using (var instancesZipFile = new ZipFile(GetType().Assembly.GetManifestResourceStream(instanceArchiveName))) {
198        var entry = instancesZipFile.GetEntry(descriptor.InstanceIdentifier);
199
200        using (var stream = instancesZipFile.GetInputStream(entry)) {
201          var parser = new QAPLIBParser();
202          parser.Parse(stream);
203          var instance = Load(parser);
204          instance.Name = id.Name;
205          instance.Description = id.Description;
206
207          if (!String.IsNullOrEmpty(descriptor.SolutionIdentifier)) {
208            var solutionsArchiveName = GetResourceName(FileName + @"\.sln\.zip");
209            using (var solutionsZipFile = new ZipFile(GetType().Assembly.GetManifestResourceStream(solutionsArchiveName))) {
210              entry = solutionsZipFile.GetEntry(descriptor.SolutionIdentifier);
211              using (var solStream = solutionsZipFile.GetInputStream(entry)) {
212                var slnParser = new QAPLIBSolutionParser();
213                slnParser.Parse(solStream, true);
214                if (slnParser.Error != null) throw slnParser.Error;
215
216                int[] assignment = slnParser.Assignment;
217                if (assignment != null && ReversedSolutions.Contains(instance.Name)) {
218                  assignment = (int[])slnParser.Assignment.Clone();
219                  for (int i = 0; i < assignment.Length; i++)
220                    assignment[slnParser.Assignment[i]] = i;
221                }
222                instance.BestKnownAssignment = assignment;
223                instance.BestKnownQuality = slnParser.Quality;
224              }
225            }
226          }
227          return instance;
228        }
229      }
230    }
231
232    public override bool CanImportData {
233      get { return true; }
234    }
235    public override QAPData ImportData(string path) {
236      var parser = new QAPLIBParser();
237      parser.Parse(path);
238      var instance = Load(parser);
239      instance.Name = Path.GetFileName(path);
240      instance.Description = "Loaded from file \"" + path + "\" on " + DateTime.Now.ToString();
241      return instance;
242    }
243
244    private QAPData Load(QAPLIBParser parser) {
245      var instance = new QAPData();
246      instance.Dimension = parser.Size;
247      instance.Distances = parser.Distances;
248      instance.Weights = parser.Weights;
249      return instance;
250    }
251
252    private string GetDescription() {
253      return "Embedded instance of plugin version " + Assembly.GetExecutingAssembly().GetCustomAttributes(typeof(AssemblyFileVersionAttribute), true).Cast<AssemblyFileVersionAttribute>().First().Version + ".";
254    }
255
256    protected virtual string GetResourceName(string fileName) {
257      return Assembly.GetExecutingAssembly().GetManifestResourceNames()
258              .Where(x => Regex.Match(x, @".*\.Data\." + fileName).Success).SingleOrDefault();
259    }
260
261    protected IEnumerable<string> GetZipContents(ZipInputStream zipFile) {
262      ZipEntry entry;
263      while ((entry = zipFile.GetNextEntry()) != null) {
264        yield return entry.Name;
265      }
266    }
267  }
268}
Note: See TracBrowser for help on using the repository browser.