Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2817-BinPackingSpeedup/HeuristicLab.Tests/HeuristicLab.Problems.Bin-Packing-3.3/3D/Instances/RandomInstanceProviderTest.cs @ 15585

Last change on this file since 15585 was 15585, checked in by rhanghof, 5 years ago

#2817:

  • Bugfixes for the line projection based extreme point creation
  • Bugfixes for the tests
File size: 15.7 KB
Line 
1using System;
2using System.IO;
3using Microsoft.VisualStudio.TestTools.UnitTesting;
4using HeuristicLab.Problems.BinPacking3D;
5using HeuristicLab.Problems.BinPacking3D.Instances;
6using System.Collections.Generic;
7using System.Linq;
8using HeuristicLab.Core;
9
10namespace HeuristicLab.Problems.BinPacking._3D.Instances.Tests {
11  [TestClass]
12  public class RandomInstanceProviderTest {
13
14    private struct Dimension {
15      public int Id { get; set; }
16      public int Width { get; set; }
17      public int Height { get; set; }
18      public int Depth { get; set; }
19    }
20
21    #region TestRandomInstanceProvider
22
23
24    /// <summary>
25    /// Tests if the generated random instance equals to the references generated by david pisinger
26    /// http://www.diku.dk/~pisinger/new3dbpp/test3dbpp.c
27    /// </summary>
28    [TestMethod]
29    [TestCategory("Problems.BinPacking.3D")]
30    [TestProperty("Time", "long")]
31    public void TestRandomInstanceProvider() {
32
33      var referenceItemLists = ReadReferenceItemLists();
34      TestRandomInstanceProviderByClass(new RandomInstanceClass1Provider(), referenceItemLists);
35      TestRandomInstanceProviderByClass(new RandomInstanceClass2Provider(), referenceItemLists);
36      TestRandomInstanceProviderByClass(new RandomInstanceClass3Provider(), referenceItemLists);
37      TestRandomInstanceProviderByClass(new RandomInstanceClass4Provider(), referenceItemLists);
38      TestRandomInstanceProviderByClass(new RandomInstanceClass5Provider(), referenceItemLists);
39      TestRandomInstanceProviderByClass(new RandomInstanceClass6Provider(), referenceItemLists);
40      TestRandomInstanceProviderByClass(new RandomInstanceClass7Provider(), referenceItemLists);
41      TestRandomInstanceProviderByClass(new RandomInstanceClass8Provider(), referenceItemLists);
42
43    }
44
45    private IDictionary<string, List<Dimension>> ReadReferenceItemLists() {
46      var itemList = new Dictionary<string, List<Dimension>>();
47      string path = @".\..\HeuristicLab.Tests\HeuristicLab.Problems.Bin-Packing-3.3\TestInstances\ReferenceInstances";
48
49      string[] files = Directory.GetFiles(path);
50      foreach (string filePath in files) {
51        string key = Path.GetFileNameWithoutExtension(filePath);
52
53        using (StreamReader reader = new StreamReader(filePath)) {
54          int lineNumber = 1;
55          List<Dimension> dimensionList = new List<Dimension>();
56          while (!reader.EndOfStream) {
57            string line = reader.ReadLine();
58            if (lineNumber > 2) {
59              string[] lineValues = line.Split('\t');
60              int id;
61              int depth;
62              int width;
63              int height;
64              Int32.TryParse(lineValues[0], out id);
65              Int32.TryParse(lineValues[1], out depth);
66              Int32.TryParse(lineValues[2], out width);
67              Int32.TryParse(lineValues[3], out height);
68              dimensionList.Add(new Dimension() {
69                Id = id,
70                Depth = depth,
71                Width = width,
72                Height = height
73              });
74            }
75            lineNumber++;
76          }
77          itemList.Add(key, dimensionList);
78        }
79      }
80      return itemList;
81    }
82
83    private void TestRandomInstanceProviderByClass(RandomInstanceProvider randomInstanceProvider, IDictionary<string, List<Dimension>> referenceItems) {
84
85      var dataDescriptors = randomInstanceProvider.GetDataDescriptors();
86      foreach (var dataDescriptor in dataDescriptors) {
87        List<Dimension> testItemDimensions = null;
88        if (referenceItems.TryGetValue(dataDescriptor.Name, out testItemDimensions)) {
89          var packingItems = randomInstanceProvider.LoadData(dataDescriptor).Items;
90          Assert.IsNotNull(packingItems);
91          Assert.AreEqual(testItemDimensions.Count, packingItems.Length);
92          for (int i = 0; i < packingItems.Length; i++) {
93            Assert.AreEqual(testItemDimensions[i].Width, packingItems[i].Width);
94            Assert.AreEqual(testItemDimensions[i].Height, packingItems[i].Height);
95            Assert.AreEqual(testItemDimensions[i].Depth, packingItems[i].Depth);
96          }
97        }
98      }
99    }
100    #endregion
101
102    #region TestExtremePointAlgorithm
103
104    /// <summary>
105    /// Constants for testing the algorithm
106    /// The test parameters are defined in the paper
107    /// </summary>
108    private const int NUMBER_OF_TEST_INSTANCES = 10;
109    private static readonly int[] TEST_CLASSES = { 1, 2 };
110    private static readonly int[] NUMBER_OF_TEST_ITEMS = { 50, 100, 150, 200 };
111
112    [TestMethod]
113    [TestCategory("Problems.BinPacking.3D")]
114    [TestProperty("Time", "long")]
115    public void TestExtremePointAlgorithmClass1() {
116      TestExtremePointAlgorithm(new RandomInstanceClass1Provider(), 1);
117    }
118
119    [TestMethod]
120    [TestCategory("Problems.BinPacking.3D")]
121    [TestProperty("Time", "long")]
122    public void TestExtremePointAlgorithmClass2() {
123      TestExtremePointAlgorithm(new RandomInstanceClass2Provider(), 2);
124    }
125
126    [TestMethod]
127    [TestCategory("Problems.BinPacking.3D")]
128    [TestProperty("Time", "long")]
129    public void TestExtremePointAlgorithmClass3() {
130      TestExtremePointAlgorithm(new RandomInstanceClass3Provider(), 3);
131    }
132
133    [TestMethod]
134    [TestCategory("Problems.BinPacking.3D")]
135    [TestProperty("Time", "long")]
136    public void TestExtremePointAlgorithmClass4() {
137      TestExtremePointAlgorithm(new RandomInstanceClass4Provider(), 4);
138    }
139
140    [TestMethod]
141    [TestCategory("Problems.BinPacking.3D")]
142    [TestProperty("Time", "long")]
143    public void TestExtremePointAlgorithmClass5() {
144      TestExtremePointAlgorithm(new RandomInstanceClass5Provider(), 5);
145    }
146
147    [TestMethod]
148    [TestCategory("Problems.BinPacking.3D")]
149    [TestProperty("Time", "long")]
150    public void TestExtremePointAlgorithmClass6() {
151      TestExtremePointAlgorithm(new RandomInstanceClass6Provider(), 6);
152    }
153
154    [TestMethod]
155    [TestCategory("Problems.BinPacking.3D")]
156    [TestProperty("Time", "long")]
157    public void TestExtremePointAlgorithmClass7() {
158      TestExtremePointAlgorithm(new RandomInstanceClass7Provider(), 7);
159    }
160
161    [TestMethod]
162    [TestCategory("Problems.BinPacking.3D")]
163    [TestProperty("Time", "long")]
164    public void TestExtremePointAlgorithmClass8() {
165      TestExtremePointAlgorithm(new RandomInstanceClass8Provider(), 8);
166    }
167
168    private void TestExtremePointAlgorithm(RandomInstanceProvider randomInstanceProvider, int @class) {
169      foreach (SortingMethod sortingMethod in Enum.GetValues(typeof(SortingMethod))) {
170        //foreach (FittingMethod fittingMethod in Enum.GetValues(typeof(FittingMethod))) {
171        FittingMethod fittingMethod = FittingMethod.FirstFit;
172        foreach (ExtremePointCreationMethod epCreationMethod in Enum.GetValues(typeof(ExtremePointCreationMethod))) {
173          TestExtremePointAlgorithmByParameters(randomInstanceProvider, @class, sortingMethod, fittingMethod, epCreationMethod);
174        }
175       
176        //}
177      }
178    }
179
180    private void TestExtremePointAlgorithmByParameters(RandomInstanceProvider randomInstanceProvider, int @class, SortingMethod sortingMethod, FittingMethod fittingMethod, ExtremePointCreationMethod epCreationMethod) {
181      var dataDescriptors = randomInstanceProvider.GetDataDescriptors();
182      var referenceValues = GetReferenceAlgorithmValues();
183      foreach (var numItems in NUMBER_OF_TEST_ITEMS) {
184        int sumNumberOfBins = 0;
185        for (int instance = 1; instance <= NUMBER_OF_TEST_INSTANCES; instance++) {
186          string name = string.Format("n={0}-id={1:00} (class={2})", numItems, instance, @class);
187          var selectedDataDescriptor = dataDescriptors.Where(dataDescriptor => dataDescriptor.Name == name);
188          Assert.IsNotNull(selectedDataDescriptor?.First());
189          var packingData = randomInstanceProvider.LoadData(selectedDataDescriptor.First());
190
191          ExtremePointAlgorithm algorithm = new ExtremePointAlgorithm();
192          algorithm.SortingMethodParameter.Value.Value = sortingMethod;
193          algorithm.FittingMethodParameter.Value.Value = fittingMethod;
194          algorithm.ExtremePointCreationMethodParameter.Value.Value = epCreationMethod;
195          algorithm.Problem.Load(packingData);
196
197          algorithm.Start();
198
199          PackingPlan<BinPacking3D.PackingPosition, PackingShape, PackingItem> bestPackingPlan = null;
200          foreach (Optimization.IResult result in algorithm.Results) {
201            if (result.Name == "Best Solution") {
202              bestPackingPlan = (PackingPlan<BinPacking3D.PackingPosition, PackingShape, PackingItem>)result.Value;
203              break;
204            }
205          }
206
207          sumNumberOfBins += bestPackingPlan.NrOfBins;
208        }
209
210        double referenceValue = 0.0;
211
212        if (referenceValues.TryGetValue(new Tuple<int, int, SortingMethod>(@class, numItems, sortingMethod), out referenceValue)) {
213          Console.WriteLine($"{numItems}-{@class}-{sortingMethod}-{epCreationMethod}: \tReference: {referenceValue} \tImplementation: {(double)sumNumberOfBins / (double)NUMBER_OF_TEST_INSTANCES} \t{(referenceValue - ((double)sumNumberOfBins / (double)NUMBER_OF_TEST_INSTANCES)):F2}");
214          Assert.AreEqual(referenceValue, (double)sumNumberOfBins / (double)NUMBER_OF_TEST_INSTANCES, 20.0);
215        }
216      }
217    }
218
219
220    /// <summary>
221    /// Returns a dictionary which contains the reference values from table 2 given by the paper https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2007-41.pdf
222    /// Dictionary<Tuple<int, int, SortingMethod>, double> -> Dictionary<Tuple<@class, number of items, SortingMethod>, value>
223    /// </summary>
224    /// <returns></returns>
225    private Dictionary<Tuple<int, int, SortingMethod>, double> GetReferenceAlgorithmValues() {
226      Dictionary<Tuple<int, int, SortingMethod>, double> referenceValues = new Dictionary<Tuple<int, int, SortingMethod>, double>();
227
228      AddToReferenceAlgorithmValuesDict(referenceValues, 1, SortingMethod.Given, new double[] { 14.6, 29.2, 40.1, 55.9});
229      AddToReferenceAlgorithmValuesDict(referenceValues, 1, SortingMethod.HeightVolume, new double[] { 15, 29.2, 39.9, 55.6 });
230      AddToReferenceAlgorithmValuesDict(referenceValues, 1, SortingMethod.VolumeHeight, new double[] { 14.4, 29.5, 40.3, 55.7 });
231      AddToReferenceAlgorithmValuesDict(referenceValues, 1, SortingMethod.AreaHeight, new double[] { 14.4, 28.3, 39.2, 53.2 });
232      AddToReferenceAlgorithmValuesDict(referenceValues, 1, SortingMethod.HeightArea, new double[] { 15, 29, 39.8, 55.1});
233      AddToReferenceAlgorithmValuesDict(referenceValues, 1, SortingMethod.ClusteredAreaHeight, new double[] { 14, 27.9, 38.1, 53 });
234      AddToReferenceAlgorithmValuesDict(referenceValues, 1, SortingMethod.ClusteredHeightArea, new double[] { 13.8, 27.4, 37.7, 52.3 });
235
236      AddToReferenceAlgorithmValuesDict(referenceValues, 4, SortingMethod.Given, new double[] { 29.7, 60.2, 88.5, 119.9 });
237      AddToReferenceAlgorithmValuesDict(referenceValues, 4, SortingMethod.HeightVolume, new double[] { 30.1, 59.6, 88.3, 120.1 });
238      AddToReferenceAlgorithmValuesDict(referenceValues, 4, SortingMethod.VolumeHeight, new double[] { 29.9, 60.4, 88.6, 119.6 });
239      AddToReferenceAlgorithmValuesDict(referenceValues, 4, SortingMethod.AreaHeight, new double[] { 30, 59.7, 88.4, 120.3 });
240      AddToReferenceAlgorithmValuesDict(referenceValues, 4, SortingMethod.HeightArea, new double[] { 30, 59.6, 88.3, 120 });
241      AddToReferenceAlgorithmValuesDict(referenceValues, 4, SortingMethod.ClusteredAreaHeight, new double[] { 29.5, 59, 86.9, 119 });
242      AddToReferenceAlgorithmValuesDict(referenceValues, 4, SortingMethod.ClusteredHeightArea, new double[] { 29.5, 59, 86.9, 118.9 });
243
244      AddToReferenceAlgorithmValuesDict(referenceValues, 5, SortingMethod.Given, new double[] { 10.1, 18.1, 24.4, 32.5 });
245      AddToReferenceAlgorithmValuesDict(referenceValues, 5, SortingMethod.HeightVolume, new double[] { 9, 16.7, 22.9, 30.7});
246      AddToReferenceAlgorithmValuesDict(referenceValues, 5, SortingMethod.VolumeHeight, new double[] { 10, 17.8, 24.5, 32.6 });
247      AddToReferenceAlgorithmValuesDict(referenceValues, 5, SortingMethod.AreaHeight, new double[] { 9.2, 16.1, 21.9, 29.5 });
248      AddToReferenceAlgorithmValuesDict(referenceValues, 5, SortingMethod.HeightArea, new double[] { 9, 16.6, 22.6, 30.5 });
249      AddToReferenceAlgorithmValuesDict(referenceValues, 5, SortingMethod.ClusteredAreaHeight, new double[] { 8.5, 15.7, 21, 28.5 });
250      AddToReferenceAlgorithmValuesDict(referenceValues, 5, SortingMethod.ClusteredHeightArea, new double[] { 8.4, 15.4, 21.1, 28.2});
251
252      AddToReferenceAlgorithmValuesDict(referenceValues, 6, SortingMethod.Given, new double[] { 11.7, 21.7, 33, 44.4});
253      AddToReferenceAlgorithmValuesDict(referenceValues, 6, SortingMethod.HeightVolume, new double[] { 10.9, 21.2, 31.8, 41.5 });
254      AddToReferenceAlgorithmValuesDict(referenceValues, 6, SortingMethod.VolumeHeight, new double[] { 11.7, 22, 34.2, 44 });
255      AddToReferenceAlgorithmValuesDict(referenceValues, 6, SortingMethod.AreaHeight, new double[] { 10.6, 20.2, 30.8, 39.5});
256      AddToReferenceAlgorithmValuesDict(referenceValues, 6, SortingMethod.HeightArea, new double[] { 10.9, 20.5, 31, 39.8 });
257      AddToReferenceAlgorithmValuesDict(referenceValues, 6, SortingMethod.ClusteredAreaHeight, new double[] { 10.2, 19.6, 29.9, 38.6 });
258      AddToReferenceAlgorithmValuesDict(referenceValues, 6, SortingMethod.ClusteredHeightArea, new double[] { 10.1, 19.8, 30.2, 38.8 });
259
260      AddToReferenceAlgorithmValuesDict(referenceValues, 7, SortingMethod.Given, new double[] { 9.4, 15.9, 19.3, 30 });
261      AddToReferenceAlgorithmValuesDict(referenceValues, 7, SortingMethod.HeightVolume, new double[] { 8.2, 14.6, 19.2, 28.1 });
262      AddToReferenceAlgorithmValuesDict(referenceValues, 7, SortingMethod.VolumeHeight, new double[] { 9.3, 15.6, 19.7, 30.2 });
263      AddToReferenceAlgorithmValuesDict(referenceValues, 7, SortingMethod.AreaHeight, new double[] { 8.1, 14.1, 18.2, 26.2 });
264      AddToReferenceAlgorithmValuesDict(referenceValues, 7, SortingMethod.HeightArea, new double[] { 8.1, 14.1, 18.9, 27,2 });
265      AddToReferenceAlgorithmValuesDict(referenceValues, 7, SortingMethod.ClusteredAreaHeight, new double[] { 7.6, 13.4, 16.9, 25 });
266      AddToReferenceAlgorithmValuesDict(referenceValues, 7, SortingMethod.ClusteredHeightArea, new double[] { 7.7, 13.3, 16.9, 24.9 });
267
268      AddToReferenceAlgorithmValuesDict(referenceValues, 8, SortingMethod.Given, new double[] { 11.6, 22, 28.5, 35.4 });
269      AddToReferenceAlgorithmValuesDict(referenceValues, 8, SortingMethod.HeightVolume, new double[] { 10.5, 20.9, 27.4, 33.9 });
270      AddToReferenceAlgorithmValuesDict(referenceValues, 8, SortingMethod.VolumeHeight, new double[] { 11.6, 22.1, 28.4, 35.4});
271      AddToReferenceAlgorithmValuesDict(referenceValues, 8, SortingMethod.AreaHeight, new double[] { 10.1, 20.3, 26.4, 32.2 });
272      AddToReferenceAlgorithmValuesDict(referenceValues, 8, SortingMethod.HeightArea, new double[] { 10.5, 20.8, 37.7, 33.9 });
273      AddToReferenceAlgorithmValuesDict(referenceValues, 8, SortingMethod.ClusteredAreaHeight, new double[] { 9.6, 19.4, 25.4, 31.4 });
274      AddToReferenceAlgorithmValuesDict(referenceValues, 8, SortingMethod.ClusteredHeightArea, new double[] { 9.5, 19.7, 25.5, 31.5 });
275
276      return referenceValues;
277    }
278
279    private void AddToReferenceAlgorithmValuesDict(Dictionary<Tuple<int, int, SortingMethod>, double> referenceValues, int @class, SortingMethod sortingMethod, double[] values) {
280      for (int i = 0; i < values.Length; i++) {
281        referenceValues.Add(new Tuple<int, int, SortingMethod>(@class, 50 + (50 * i), sortingMethod), values[i]);
282      }
283     
284    }
285
286
287    #endregion
288  }
289
290}
Note: See TracBrowser for help on using the repository browser.