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

Last change on this file since 8553 was 8553, checked in by abeham, 7 years ago

#1890: Updated best known qualities of missing QAPLIB solutions

File size: 8.1 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    private static HashSet<string> reversedSolutions = new HashSet<string>(new string[] {
35      "bur26a",
36      "bur26b",
37      "bur26c",
38      "bur26d",
39      "bur26e",
40      "bur26f",
41      "bur26g",
42      "bur26h",
43      "chr12a",
44      "chr12b",
45      "chr12c",
46      "chr15a",
47      "chr15b",
48      "chr15c",
49      "chr18a",
50      "chr18b",
51      "chr20a",
52      "chr20b",
53      "chr20c",
54      "chr22a",
55      "chr22b",
56      "chr25a",
57      "esc16a",
58      "esc16b",
59      "esc16c",
60      "esc16d",
61      "esc16e",
62      "esc16g",
63      "esc16h",
64      "esc16i",
65      "esc16j",
66      "esc32a",
67      "esc32b",
68      "esc32c",
69      "esc32d",
70      "esc32e",
71      "esc32f",
72      "esc32g",
73      "esc32h",
74      "had12",
75      "had14",
76      "had16",
77      "had18",
78      "had20",
79      "kra32",
80      "lipa20a",
81      "lipa30a",
82      "lipa40a",
83      "lipa50a",
84      "lipa60a",
85      "lipa70a",
86      "lipa80a",
87      "lipa90a",
88      "nug12",
89      "nug14",
90      "nug15",
91      "nug16a",
92      "nug16b",
93      "nug17",
94      "nug18",
95      "nug20",
96      "nug21",
97      "nug22",
98      "nug24",
99      "nug25",
100      "nug27",
101      "nug28",
102      "rou12",
103      "rou15",
104      "rou20",
105      "scr12",
106      "scr15",
107      "scr20",
108      "sko100a",
109      "sko100b",
110      "sko100c",
111      "sko100d",
112      "sko100e",
113      "sko100f",
114      "sko49",
115      "sko81",
116      "sko90",
117      "ste36a",
118      "ste36b",
119      "tai100a",
120      "tai100b",
121      "tai12a",
122      "tai12b",
123      "tai150b",
124      "tai15a",
125      "tai15b",
126      "tai17a",
127      "tai20a",
128      "tai20b",
129      "tai256c",
130      "tai25a",
131      "tai25b",
132      "tai30a",
133      "tai30b",
134      "tai35a",
135      "tai35b",
136      "tai40a",
137      "tai40b",
138      "tai50a",
139      "tai50b",
140      "tai60a",
141      "tai60b",
142      "tai64c",
143      "tai80a",
144      "tai80b",
145      "wil100"
146    });
147    #endregion
148
149    public override string Name {
150      get { return "QAPLIB"; }
151    }
152
153    public override string Description {
154      get { return "Quadratic Assignment Problem Library"; }
155    }
156
157    public override Uri WebLink {
158      get { return new Uri("http://www.seas.upenn.edu/qaplib/"); }
159    }
160
161    public override string ReferencePublication {
162      get {
163        return @"R. E. Burkard, S. E. Karisch, and F. Rendl. 1997.
164QAPLIB - A Quadratic Assignment Problem Library.
165Journal of Global Optimization, 10, pp. 391-403.";
166      }
167    }
168
169    private const string FileName = "qap";
170
171    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
172      Dictionary<string, string> solutions = new Dictionary<string, string>();
173      var solutionsArchiveName = GetResourceName(FileName + @"\.sln\.zip");
174      if (!String.IsNullOrEmpty(solutionsArchiveName)) {
175        using (var solutionsZipFile = new ZipInputStream(GetType().Assembly.GetManifestResourceStream(solutionsArchiveName))) {
176          foreach (var entry in GetZipContents(solutionsZipFile))
177            solutions.Add(Path.GetFileNameWithoutExtension(entry) + ".dat", entry);
178        }
179      }
180      var instanceArchiveName = GetResourceName(FileName + @"\.dat\.zip");
181      if (String.IsNullOrEmpty(instanceArchiveName)) yield break;
182
183      using (var instanceStream = new ZipInputStream(GetType().Assembly.GetManifestResourceStream(instanceArchiveName))) {
184        foreach (var entry in GetZipContents(instanceStream).OrderBy(x => x)) {
185          yield return new QAPLIBDataDescriptor(Path.GetFileNameWithoutExtension(entry), GetDescription(), entry, solutions.ContainsKey(entry) ? solutions[entry] : String.Empty);
186        }
187      }
188    }
189
190    public override QAPData LoadData(IDataDescriptor id) {
191      var descriptor = (QAPLIBDataDescriptor)id;
192      var instanceArchiveName = GetResourceName(FileName + @"\.dat\.zip");
193      using (var instancesZipFile = new ZipFile(GetType().Assembly.GetManifestResourceStream(instanceArchiveName))) {
194        var entry = instancesZipFile.GetEntry(descriptor.InstanceIdentifier);
195
196        using (var stream = instancesZipFile.GetInputStream(entry)) {
197          var parser = new QAPLIBParser();
198          parser.Parse(stream);
199          var instance = Load(parser);
200          instance.Name = id.Name;
201          instance.Description = id.Description;
202
203          if (!String.IsNullOrEmpty(descriptor.SolutionIdentifier)) {
204            var solutionsArchiveName = GetResourceName(FileName + @"\.sln\.zip");
205            using (var solutionsZipFile = new ZipFile(GetType().Assembly.GetManifestResourceStream(solutionsArchiveName))) {
206              entry = solutionsZipFile.GetEntry(descriptor.SolutionIdentifier);
207              using (var solStream = solutionsZipFile.GetInputStream(entry)) {
208                var slnParser = new QAPLIBSolutionParser();
209                slnParser.Parse(solStream, true);
210                if (slnParser.Error != null) throw slnParser.Error;
211
212                int[] assignment = slnParser.Assignment;
213                if (assignment != null && reversedSolutions.Contains(instance.Name)) {
214                  assignment = (int[])slnParser.Assignment.Clone();
215                  for (int i = 0; i < assignment.Length; i++)
216                    assignment[slnParser.Assignment[i]] = i;
217                }
218                instance.BestKnownAssignment = assignment;
219                instance.BestKnownQuality = slnParser.Quality;
220              }
221            }
222          }
223          return instance;
224        }
225      }
226    }
227
228    public override bool CanImportData {
229      get { return true; }
230    }
231    public override QAPData ImportData(string path) {
232      var parser = new QAPLIBParser();
233      parser.Parse(path);
234      var instance = Load(parser);
235      instance.Name = Path.GetFileName(path);
236      instance.Description = "Loaded from file \"" + path + "\" on " + DateTime.Now.ToString();
237      return instance;
238    }
239
240    private QAPData Load(QAPLIBParser parser) {
241      var instance = new QAPData();
242      instance.Dimension = parser.Size;
243      instance.Distances = parser.Distances;
244      instance.Weights = parser.Weights;
245      return instance;
246    }
247
248    private string GetDescription() {
249      return "Embedded instance of plugin version " + Assembly.GetExecutingAssembly().GetCustomAttributes(typeof(AssemblyFileVersionAttribute), true).Cast<AssemblyFileVersionAttribute>().First().Version + ".";
250    }
251
252    protected virtual string GetResourceName(string fileName) {
253      return Assembly.GetExecutingAssembly().GetManifestResourceNames()
254              .Where(x => Regex.Match(x, @".*\.Data\." + fileName).Success).SingleOrDefault();
255    }
256
257    protected IEnumerable<string> GetZipContents(ZipInputStream zipFile) {
258      ZipEntry entry;
259      while ((entry = zipFile.GetNextEntry()) != null) {
260        yield return entry.Name;
261      }
262    }
263  }
264}
Note: See TracBrowser for help on using the repository browser.