Free cookie consent management tool by TermsFeed Policy Generator

source: branches/OaaS/HeuristicLab.Tests/HeuristicLab.Problems.QuadraticAssignment-3.3/QAPLIBInstancesTest.cs @ 15325

Last change on this file since 15325 was 8092, checked in by abeham, 12 years ago

#1856: Added unit test for lower bound, made it more obvious that last element is not left out

File size: 8.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.Linq;
25using System.Text;
26using HeuristicLab.Problems.Instances.QAPLIB;
27using Microsoft.VisualStudio.TestTools.UnitTesting;
28
29namespace HeuristicLab.Problems.QuadraticAssignment.Tests_33 {
30  [TestClass]
31  public class QAPLIBInstancesTest {
32    #region instances
33    private static Dictionary<string, double> qaplibInstances = new Dictionary<string, double>() {
34      { "bur26a", 5426670 },
35      { "bur26b", 3817852 },
36      { "bur26c", 5426795 },
37      { "bur26d", 3821225 },
38      { "bur26e", 5386879 },
39      { "bur26f", 3782044 },
40      { "bur26g", 10117172 },
41      { "bur26h", 7098658 },
42      { "chr12a", 9552 },
43      { "chr12b", 9742 },
44      { "chr12c", 11156 },
45      { "chr15a", 9896 },
46      { "chr15b", 7990 },
47      { "chr15c", 9504 },
48      { "chr18a", 11098 },
49      { "chr18b", 1534 },
50      { "chr20a", 2192 },
51      { "chr20b", 2298 },
52      { "chr20c", 14142 },
53      { "chr22a", 6156 },
54      { "chr22b", 6194 },
55      { "chr25a", 3796 },
56      { "els19", 17212548 },
57      { "esc16a", 68 },
58      { "esc16b", 292 },
59      { "esc16c", 160 },
60      { "esc16d", 16 },
61      { "esc16e", 28 },
62      { "esc16f", 0 },
63      { "esc16g", 26 },
64      { "esc16h", 996 },
65      { "esc16i", 14 },
66      { "esc16j", 8 },
67      { "esc32a", 130 },
68      { "esc32b", 168 },
69      { "esc32c", 642 },
70      { "esc32d", 200 },
71      { "esc32e", 2 },
72      { "esc32f", 2 },
73      { "esc32g", 6 },
74      { "esc32h", 438 },
75      { "esc64", 116 },
76      { "esc128", 64 },
77      { "had12", 1652 },
78      { "had14", 2724 },
79      { "had16", 3720 },
80      { "had18", 5358 },
81      { "had20", 6922 },
82      { "kra30a", 88900 },
83      { "kra30b", 91420 },
84      { "kra32", 88700 },
85      { "lipa20a", 3683 },
86      { "lipa20b", 27076 },
87      { "lipa30a", 13178 },
88      { "lipa30b", 151426 },
89      { "lipa40a", 31538 },
90      { "lipa40b", 476581 },
91      { "lipa50a", 62093 },
92      { "lipa50b", 1210244 },
93      { "lipa60a", 107218 },
94      { "lipa60b", 2520135 },
95      { "lipa70a", 169755 },
96      { "lipa70b", 4603200 },
97      { "lipa80a", 253195 },
98      { "lipa80b", 7763962 },
99      { "lipa90a", 360630 },
100      { "lipa90b", 12490441 },
101      { "nug12", 578 },
102      { "nug14", 1014 },
103      { "nug15", 1150 },
104      { "nug16a", 1610 },
105      { "nug16b", 1240 },
106      { "nug17", 1732 },
107      { "nug18", 1930 },
108      { "nug20", 2570 },
109      { "nug21", 2438 },
110      { "nug22", 3596 },
111      { "nug24", 3488 },
112      { "nug25", 3744 },
113      { "nug27", 5234 },
114      { "nug28", 5166 },
115      { "nug30", 6124 },
116      { "rou12", 235528 },
117      { "rou15", 354210 },
118      { "rou20", 725522 },
119      { "scr12", 31410 },
120      { "scr15", 51140 },
121      { "scr20", 110030 },
122      { "sko42", 15812 },
123      { "sko49", 23386 },
124      { "sko56", 34458 },
125      { "sko64", 48498 },
126      { "sko72", 66256 },
127      { "sko81", 90998 },
128      { "sko90", 115534 },
129      { "sko100a", 152002 },
130      { "sko100b", 153890 },
131      { "sko100c", 147862 },
132      { "sko100d", 149576 },
133      { "sko100e", 149150 },
134      { "sko100f", 149036 },
135      { "ste36a", 9526 },
136      { "ste36b", 15852 },
137      { "ste36c", 8239110 },
138      { "tai12a", 224416 },
139      { "tai12b", 39464925 },
140      { "tai15a", 388214 },
141      { "tai15b", 51765268 },
142      { "tai17a", 491812 },
143      { "tai20a", 703482 },
144      { "tai20b", 122455319 },
145      { "tai25a", 1167256 },
146      { "tai25b", 344355646 },
147      { "tai30a", 1818146 },
148      { "tai30b", 637117113 },
149      { "tai35a", 2422002 },
150      { "tai35b", 283315445 },
151      { "tai40a", 3139370 },
152      { "tai40b", 637250948 },
153      { "tai50a", 4938796 },
154      { "tai50b", 458821517 },
155      { "tai60a", 7208572  },
156      { "tai60b", 608215054 },
157      { "tai64c", 1855928 },
158      { "tai80a", 13557864 },
159      { "tai80b", 818415043 },
160      { "tai100a", 21052466 },
161      { "tai100b", 1185996137 },
162      { "tai150b", 498896643 },
163      { "tai256c", 44759294 },
164      { "tho30", 149936 },
165      { "tho40", 240516 },
166      { "tho150", 8133398 },
167      { "wil50", 48816 },
168      { "wil100", 273038 }
169    };
170    private static Dictionary<string, double> lowerBounds = new Dictionary<string, double>() {
171      { "bur26a", 5315200 },
172      { "bur26f", 3706888 },
173      { "chr25a", 2765 },
174      { "els19", 11971949 },
175      { "esc32a", 35 },
176      { "esc32e", 0 },
177      { "had20", 6166 },
178      { "kra32", 67390 },
179      { "lipa50a", 62020 },
180      { "lipa50b", 1210244 },
181      { "nug30", 4539 },
182      { "scr20", 86766 },
183      { "sko42", 11311 },
184      { "tai35a", 1951207 },
185      { "tai35b", 30866283 },
186      { "tai100a", 15824355 }
187    };
188    #endregion
189
190    [TestMethod]
191    public void TestQAPLIBInstances() {
192      var provider = new QAPLIBInstanceProvider();
193      var qap = new QuadraticAssignmentProblem();
194      var failedInstances = new StringBuilder();
195
196      var instances = provider.GetDataDescriptors();
197      Assert.IsTrue(instances.Any(), "No instances could be found.");
198
199      foreach (var instance in instances) {
200        try {
201          qap.Load(provider.LoadData(instance));
202        } catch (Exception ex) {
203          failedInstances.AppendLine(instance + ": " + ex.Message);
204        }
205      }
206      Assert.IsTrue(failedInstances.Length == 0, "Following instances failed: " + Environment.NewLine + failedInstances.ToString());
207    }
208
209    [TestMethod]
210    public void TestQAPLIBSolutions() {
211      var provider = new QAPLIBInstanceProvider();
212      var qap = new QuadraticAssignmentProblem();
213      var failedInstances = new StringBuilder();
214
215      var instances = provider.GetDataDescriptors();
216      Assert.IsTrue(instances.Any(), "No instances could be found.");
217
218      foreach (var instance in instances) {
219        qap.Load(provider.LoadData(instance));
220        if (qaplibInstances.ContainsKey(instance.Name)
221          && qap.BestKnownQuality != null && qap.BestKnownQuality.Value != qaplibInstances[instance.Name])
222          failedInstances.AppendLine(instance.Name + ": " + qap.BestKnownQuality.Value.ToString() + " vs " + qaplibInstances[instance.Name]);
223      }
224      Assert.IsTrue(failedInstances.Length == 0, "Following instances/solutions have suspicious best quality: " + Environment.NewLine + failedInstances.ToString());
225    }
226
227    [TestMethod]
228    public void TestQAPLIBLowerBounds() {
229      var provider = new QAPLIBInstanceProvider();
230      var qap = new QuadraticAssignmentProblem();
231      var failedInstances = new StringBuilder();
232
233      var instances = provider.GetDataDescriptors();
234      Assert.IsTrue(instances.Any(), "No instances could be found.");
235
236      foreach (var instance in instances) {
237        if (lowerBounds.ContainsKey(instance.Name)) {
238          qap.Load(provider.LoadData(instance));
239          if (qap.LowerBound.Value != lowerBounds[instance.Name])
240            failedInstances.AppendLine(instance.Name + ": The Gilmore-Lawler lower bound is not valid.");
241        }
242      }
243      Assert.IsTrue(failedInstances.Length == 0, "Following instances failed for the GLB calculation: " + Environment.NewLine + failedInstances.ToString());
244    }
245  }
246}
Note: See TracBrowser for help on using the repository browser.