Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2817-BinPackingSpeedup/HeuristicLab.Tests/HeuristicLab.Problems.Bin-Packing-3.3/AlgorithmTest.cs @ 15423

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

#2817: - Now the new RandomInstanceProvider creates the same instances as in the specification given by Martello, Pisinger and Vigo.

  • Now the unit tests are testing the new RandomInstanceProvider.
File size: 9.5 KB
Line 
1using System;
2using System.IO;
3using Microsoft.VisualStudio.TestTools.UnitTesting;
4using HeuristicLab.Problems.BinPacking3D;
5using System.Collections.Generic;
6using System.Linq;
7using HeuristicLab.Core;
8
9namespace HeuristicLab.Problems.BinPacking.Tests {
10  [TestClass]
11  public class AlgorithmTest {
12
13    private struct Dimension {
14      public int Id { get; set; }
15      public int Width { get; set; }
16      public int Height { get; set; }
17      public int Depth { get; set; }
18    }
19
20    #region TestRandomInstanceProvider
21
22
23    /// <summary>
24    /// Tests if the generated random instance equals to the references generated by david pisinger
25    /// http://www.diku.dk/~pisinger/new3dbpp/test3dbpp.c
26    /// </summary>
27    [TestMethod]
28    [TestCategory("Problems.BinPacking")]
29    public void TestRandomInstanceProvider() {
30     
31      var referenceItemLists = ReadReferenceItemLists();
32      TestRandomInstanceProviderByClass(new RandomInstanceClass1ProviderWithSRand(), referenceItemLists);
33      TestRandomInstanceProviderByClass(new RandomInstanceClass2ProviderWithSRand(), referenceItemLists);
34      TestRandomInstanceProviderByClass(new RandomInstanceClass3ProviderWithSRand(), referenceItemLists);
35      TestRandomInstanceProviderByClass(new RandomInstanceClass4ProviderWithSRand(), referenceItemLists);
36      TestRandomInstanceProviderByClass(new RandomInstanceClass5ProviderWithSRand(), referenceItemLists);
37      TestRandomInstanceProviderByClass(new RandomInstanceClass6ProviderWithSRand(), referenceItemLists);
38      TestRandomInstanceProviderByClass(new RandomInstanceClass7ProviderWithSRand(), referenceItemLists);
39      TestRandomInstanceProviderByClass(new RandomInstanceClass8ProviderWithSRand(), referenceItemLists);
40     
41    }
42
43    private IDictionary<string, List<Dimension>> ReadReferenceItemLists() {
44      var itemList = new Dictionary<string, List<Dimension>>();
45      string path = @"C:\HEAL\BinPacking\Algorithm\export";//todo which location can be used for storing the reference files? At the moment their location can be found on the local disc
46
47      string[] files = Directory.GetFiles(path);
48      foreach (string filePath in files) {
49        string key = Path.GetFileNameWithoutExtension(filePath);
50
51        using (StreamReader reader = new StreamReader(filePath)) {
52          int lineNumber = 1;
53          List<Dimension> dimensionList = new List<Dimension>();
54          while (!reader.EndOfStream) {
55            string line = reader.ReadLine();
56            if (lineNumber > 2) {
57              string[] lineValues = line.Split('\t');
58              int id;
59              int depth;
60              int width;
61              int height;
62              Int32.TryParse(lineValues[0], out id);
63              Int32.TryParse(lineValues[1], out depth);
64              Int32.TryParse(lineValues[2], out width);
65              Int32.TryParse(lineValues[3], out height);
66              dimensionList.Add(new Dimension() {
67                Id = id,
68                Depth = depth,
69                Width = width,
70                Height = height
71              });
72            }
73            lineNumber++;
74          }
75          itemList.Add(key, dimensionList);
76        }
77      }
78      return itemList;
79    }
80
81    private void TestRandomInstanceProviderByClass(RandomInstanceProviderWithSRand randomInstanceProvider, IDictionary<string, List<Dimension>> referenceItems) {
82
83      var dataDescriptors = randomInstanceProvider.GetDataDescriptors();
84      foreach (var dataDescriptor in dataDescriptors) {
85        List<Dimension> testItemDimensions = null;
86        if (referenceItems.TryGetValue(dataDescriptor.Name, out testItemDimensions)) {
87          var packingItems = randomInstanceProvider.LoadData(dataDescriptor).Items;
88          Assert.IsNotNull(packingItems);
89          Assert.AreEqual(testItemDimensions.Count, packingItems.Length);
90          for (int i = 0; i < packingItems.Length; i++) {
91            Assert.AreEqual(testItemDimensions[i].Width, packingItems[i].Width);
92            Assert.AreEqual(testItemDimensions[i].Height, packingItems[i].Height);
93            Assert.AreEqual(testItemDimensions[i].Depth, packingItems[i].Depth);
94          }
95        }
96      }
97    }
98    #endregion
99
100    #region TestExtremePointAlgorithm
101
102    /// <summary>
103    /// Constants for testing the algorithm
104    /// The test parameter are defined in the paper
105    /// </summary>
106    private const int NUMBER_OF_TEST_INSTANCES = 10;
107    private static readonly int[] TEST_CLASSES = { 1, 2 };
108    private static readonly int[] NUMBER_OF_TEST_ITEMS = { 50, 100, 150, 200 };
109
110    [TestMethod]
111    [TestCategory("Problems.BinPacking")]
112    public void TestExtremePointAlgorithm() {
113      TestExtremePointAlgorithmByParameters(new RandomInstanceClass1ProviderWithSRand(), 1, SortingMethod.Given, FittingMethod.FirstFit);
114
115
116    }
117
118    private void TestExtremePointAlgorithmByParameters(RandomInstanceProviderWithSRand randomInstanceProvider, int @class, SortingMethod sortingMethod, FittingMethod fittingMethod) {
119      var dataDescriptors = randomInstanceProvider.GetDataDescriptors();
120      var referenceValues = GetReferenceAlgorithmValues();
121      foreach (var numItems in NUMBER_OF_TEST_ITEMS) {
122        int sumNumberOfBins = 0;
123        for (int instance = 1; instance <= NUMBER_OF_TEST_INSTANCES; instance++) {
124          string name = string.Format("n={0}-id={1:00} (class={2})", numItems, instance, @class);
125          var selectedDataDescriptor = dataDescriptors.Where(dataDescriptor => dataDescriptor.Name == name);
126          Assert.IsNotNull(selectedDataDescriptor?.First());
127          var packingData = randomInstanceProvider.LoadData(selectedDataDescriptor.First());
128
129          ExtremePointAlgorithm algorithm = new ExtremePointAlgorithm();
130          algorithm.SortingMethodParameter.Value.Value = sortingMethod;
131          algorithm.FittingMethodParameter.Value.Value = fittingMethod;
132          algorithm.Problem.Load(packingData);
133
134          algorithm.Start();
135
136          PackingPlan<BinPacking3D.PackingPosition, PackingShape, PackingItem> bestPackingPlan = null;
137          foreach (Optimization.IResult result in algorithm.Results) {
138            if (result.Name == "Best Solution") {
139              bestPackingPlan = (PackingPlan<BinPacking3D.PackingPosition, PackingShape, PackingItem>)result.Value;
140              break;
141            }
142          }
143
144          sumNumberOfBins += bestPackingPlan.NrOfBins;
145        }
146
147        double referenceValue = 0.0;
148       
149        if (referenceValues.TryGetValue(new Tuple<int, int, SortingMethod>(@class, numItems, sortingMethod), out referenceValue)) {
150          Console.WriteLine($"{numItems}: {referenceValue} {(double)sumNumberOfBins / (double)NUMBER_OF_TEST_INSTANCES}");
151          Assert.AreEqual(referenceValue, (double)sumNumberOfBins / (double)NUMBER_OF_TEST_INSTANCES, 1.0);
152        }
153      }
154    }
155
156
157    /// <summary>
158    /// Returns a dictionary which contains the reference values from table 2 given by the paper https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2007-41.pdf
159    /// </summary>
160    /// <returns></returns>
161    private Dictionary<Tuple<int, int, SortingMethod>, double> GetReferenceAlgorithmValues() {
162      Dictionary<Tuple<int, int, SortingMethod>, double> referenceValues = new Dictionary<Tuple<int, int, SortingMethod>, double>();
163
164      referenceValues.Add(new Tuple<int, int, SortingMethod>(1, 50, SortingMethod.Given), 14.6);
165      referenceValues.Add(new Tuple<int, int, SortingMethod>(1, 100, SortingMethod.Given), 29.2);
166      referenceValues.Add(new Tuple<int, int, SortingMethod>(1, 150, SortingMethod.Given), 40.1);
167      referenceValues.Add(new Tuple<int, int, SortingMethod>(1, 200, SortingMethod.Given), 55.9);
168
169      referenceValues.Add(new Tuple<int, int, SortingMethod>(1, 50, SortingMethod.HeightVolume), 15);
170      referenceValues.Add(new Tuple<int, int, SortingMethod>(1, 100, SortingMethod.HeightVolume), 29.2);
171      referenceValues.Add(new Tuple<int, int, SortingMethod>(1, 150, SortingMethod.HeightVolume), 39.9);
172      referenceValues.Add(new Tuple<int, int, SortingMethod>(1, 200, SortingMethod.HeightVolume), 55.6);
173
174      referenceValues.Add(new Tuple<int, int, SortingMethod>(1, 50, SortingMethod.VolumeHeight), 14.4);
175      referenceValues.Add(new Tuple<int, int, SortingMethod>(1, 100, SortingMethod.VolumeHeight), 29.5);
176      referenceValues.Add(new Tuple<int, int, SortingMethod>(1, 150, SortingMethod.VolumeHeight), 40.3);
177      referenceValues.Add(new Tuple<int, int, SortingMethod>(1, 200, SortingMethod.VolumeHeight), 55.7);
178
179      referenceValues.Add(new Tuple<int, int, SortingMethod>(1, 50, SortingMethod.AreaHeight), 14.4);
180      referenceValues.Add(new Tuple<int, int, SortingMethod>(1, 100, SortingMethod.AreaHeight), 28.3);
181      referenceValues.Add(new Tuple<int, int, SortingMethod>(1, 150, SortingMethod.AreaHeight), 39.2);
182      referenceValues.Add(new Tuple<int, int, SortingMethod>(1, 200, SortingMethod.AreaHeight), 53.2);
183
184      referenceValues.Add(new Tuple<int, int, SortingMethod>(1, 50, SortingMethod.HeightArea), 15);
185      referenceValues.Add(new Tuple<int, int, SortingMethod>(1, 100, SortingMethod.HeightArea), 29);
186      referenceValues.Add(new Tuple<int, int, SortingMethod>(1, 150, SortingMethod.HeightArea), 39.8);
187      referenceValues.Add(new Tuple<int, int, SortingMethod>(1, 200, SortingMethod.HeightArea), 55.1);
188
189
190      var s = referenceValues[new Tuple<int, int, SortingMethod>(1, 200, SortingMethod.HeightArea)];
191
192      return referenceValues;
193    }
194
195
196    #endregion
197  }
198
199}
Note: See TracBrowser for help on using the repository browser.