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

Last change on this file was 15989, checked in by rhanghof, 6 years ago

#2817:

  • Adjusted the unit tests
  • Refactoring of the sorter
  • Bugfix on the BinPackerResidualSpaceBestFit packer
File size: 13.0 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 TestExtremePointAlgorithm
22
23    /// <summary>
24    /// Constants for testing the algorithm
25    /// The test parameters are defined in the paper
26    /// </summary>
27    private const int NUMBER_OF_TEST_INSTANCES = 10;
28    private static readonly int[] TEST_CLASSES = { 1, 2 };
29    private static readonly int[] NUMBER_OF_TEST_ITEMS = { 50, 100, 150, 200 };
30
31    [TestMethod]
32    [TestCategory("Problems.BinPacking.3D")]
33    [TestProperty("Time", "long")]
34    public void TestExtremePointAlgorithmClass1() {
35      TestExtremePointAlgorithm(new RandomInstanceClass1Provider(), 1);
36    }
37
38    [TestMethod]
39    [TestCategory("Problems.BinPacking.3D")]
40    [TestProperty("Time", "long")]
41    public void TestExtremePointAlgorithmClass2() {
42      TestExtremePointAlgorithm(new RandomInstanceClass2Provider(), 2);
43    }
44
45    [TestMethod]
46    [TestCategory("Problems.BinPacking.3D")]
47    [TestProperty("Time", "long")]
48    public void TestExtremePointAlgorithmClass3() {
49      TestExtremePointAlgorithm(new RandomInstanceClass3Provider(), 3);
50    }
51
52    [TestMethod]
53    [TestCategory("Problems.BinPacking.3D")]
54    [TestProperty("Time", "long")]
55    public void TestExtremePointAlgorithmClass4() {
56      TestExtremePointAlgorithm(new RandomInstanceClass4Provider(), 4);
57    }
58
59    [TestMethod]
60    [TestCategory("Problems.BinPacking.3D")]
61    [TestProperty("Time", "long")]
62    public void TestExtremePointAlgorithmClass5() {
63      TestExtremePointAlgorithm(new RandomInstanceClass5Provider(), 5);
64    }
65
66    [TestMethod]
67    [TestCategory("Problems.BinPacking.3D")]
68    [TestProperty("Time", "long")]
69    public void TestExtremePointAlgorithmClass6() {
70      TestExtremePointAlgorithm(new RandomInstanceClass6Provider(), 6);
71    }
72
73    [TestMethod]
74    [TestCategory("Problems.BinPacking.3D")]
75    [TestProperty("Time", "long")]
76    public void TestExtremePointAlgorithmClass7() {
77      TestExtremePointAlgorithm(new RandomInstanceClass7Provider(), 7);
78    }
79
80    [TestMethod]
81    [TestCategory("Problems.BinPacking.3D")]
82    [TestProperty("Time", "long")]
83    public void TestExtremePointAlgorithmClass8() {
84      TestExtremePointAlgorithm(new RandomInstanceClass8Provider(), 8);
85    }
86
87    private void TestExtremePointAlgorithm(RandomInstanceProvider randomInstanceProvider, int @class) {
88      foreach (SortingMethod sortingMethod in Enum.GetValues(typeof(SortingMethod))) {
89        //foreach (FittingMethod fittingMethod in Enum.GetValues(typeof(FittingMethod))) {
90        FittingMethod fittingMethod = FittingMethod.FreeVolumeBestFit;
91        TestExtremePointAlgorithmByParameters(randomInstanceProvider, @class, sortingMethod, fittingMethod, ExtremePointCreationMethod.LineProjection);
92
93        /*foreach (ExtremePointCreationMethod epCreationMethod in Enum.GetValues(typeof(ExtremePointCreationMethod))) {
94          TestExtremePointAlgorithmByParameters(randomInstanceProvider, @class, sortingMethod, fittingMethod, epCreationMethod);
95        }*/
96
97        //}
98      }
99    }
100
101    private void TestExtremePointAlgorithmByParameters(RandomInstanceProvider randomInstanceProvider, int @class, SortingMethod sortingMethod, FittingMethod fittingMethod, ExtremePointCreationMethod epCreationMethod) {
102      var dataDescriptors = randomInstanceProvider.GetDataDescriptors();
103      var referenceValues = GetReferenceAlgorithmValues();
104      foreach (var numItems in NUMBER_OF_TEST_ITEMS) {
105        int sumNumberOfBins = 0;
106
107        double referenceValue = 0.0;
108        if (referenceValues.TryGetValue(new Tuple<int, int, SortingMethod>(@class, numItems, sortingMethod), out referenceValue)) {
109          for (int instance = 1; instance <= NUMBER_OF_TEST_INSTANCES; instance++) {
110            string name = string.Format("n={0}-id={1:00} (class={2})", numItems, instance, @class);
111            var selectedDataDescriptor = dataDescriptors.Where(dataDescriptor => dataDescriptor.Name == name);
112            Assert.IsNotNull(selectedDataDescriptor?.First());
113            var packingData = randomInstanceProvider.LoadData(selectedDataDescriptor.First());
114
115            ExtremePointAlgorithm algorithm = new ExtremePointAlgorithm();
116            algorithm.SortingMethodParameter.Value.Value = sortingMethod;
117            algorithm.FittingMethodParameter.Value.Value = fittingMethod;
118            algorithm.ExtremePointCreationMethodParameter.Value.Value = epCreationMethod;
119            algorithm.SortBySequenceGroupParameter.Value.Value = false;
120
121            algorithm.Problem.UseStackingConstraintsParameter.Value.Value = false;
122            algorithm.Problem.Load(packingData);
123
124            algorithm.Start();
125
126            PackingPlan<BinPacking3D.PackingPosition, PackingShape, PackingItem> bestPackingPlan = null;
127            foreach (Optimization.IResult result in algorithm.Results) {
128              if (result.Name == "Best Solution") {
129                bestPackingPlan = (PackingPlan<BinPacking3D.PackingPosition, PackingShape, PackingItem>)result.Value;
130                break;
131              }
132            }
133
134            sumNumberOfBins += bestPackingPlan.NrOfBins;
135          }
136       
137          //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};");
138          var implementation = (double)sumNumberOfBins / (double)NUMBER_OF_TEST_INSTANCES;
139          var enhancement = (referenceValue * 100 / implementation) - 100;
140          Console.WriteLine($"{@class};{numItems};{sortingMethod};{enhancement:F2} %;{referenceValue};{implementation}");
141//          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}");
142          //Assert.AreEqual(referenceValue, (double)sumNumberOfBins / (double)NUMBER_OF_TEST_INSTANCES, 20.0);
143        }
144      }
145    }
146
147
148    /// <summary>
149    /// Returns a dictionary which contains the reference values from table 2 given by the paper https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2007-41.pdf
150    /// Dictionary<Tuple<int, int, SortingMethod>, double> -> Dictionary<Tuple<@class, number of items, SortingMethod>, value>
151    /// </summary>
152    /// <returns></returns>
153    private Dictionary<Tuple<int, int, SortingMethod>, double> GetReferenceAlgorithmValues() {
154      Dictionary<Tuple<int, int, SortingMethod>, double> referenceValues = new Dictionary<Tuple<int, int, SortingMethod>, double>();
155
156      AddToReferenceAlgorithmValuesDict(referenceValues, 1, SortingMethod.Given, new double[] { 14.6, 29.2, 40.1, 55.9});
157      AddToReferenceAlgorithmValuesDict(referenceValues, 1, SortingMethod.HeightVolume, new double[] { 15, 29.2, 39.9, 55.6 });
158      AddToReferenceAlgorithmValuesDict(referenceValues, 1, SortingMethod.VolumeHeight, new double[] { 14.4, 29.5, 40.3, 55.7 });
159      AddToReferenceAlgorithmValuesDict(referenceValues, 1, SortingMethod.AreaHeight, new double[] { 14.4, 28.3, 39.2, 53.2 });
160      AddToReferenceAlgorithmValuesDict(referenceValues, 1, SortingMethod.HeightArea, new double[] { 15, 29, 39.8, 55.1});
161      AddToReferenceAlgorithmValuesDict(referenceValues, 1, SortingMethod.ClusteredAreaHeight, new double[] { 14, 27.9, 38.1, 53 });
162      AddToReferenceAlgorithmValuesDict(referenceValues, 1, SortingMethod.ClusteredHeightArea, new double[] { 13.8, 27.4, 37.7, 52.3 });
163
164      AddToReferenceAlgorithmValuesDict(referenceValues, 4, SortingMethod.Given, new double[] { 29.7, 60.2, 88.5, 119.9 });
165      AddToReferenceAlgorithmValuesDict(referenceValues, 4, SortingMethod.HeightVolume, new double[] { 30.1, 59.6, 88.3, 120.1 });
166      AddToReferenceAlgorithmValuesDict(referenceValues, 4, SortingMethod.VolumeHeight, new double[] { 29.9, 60.4, 88.6, 119.6 });
167      AddToReferenceAlgorithmValuesDict(referenceValues, 4, SortingMethod.AreaHeight, new double[] { 30, 59.7, 88.4, 120.3 });
168      AddToReferenceAlgorithmValuesDict(referenceValues, 4, SortingMethod.HeightArea, new double[] { 30, 59.6, 88.3, 120 });
169      AddToReferenceAlgorithmValuesDict(referenceValues, 4, SortingMethod.ClusteredAreaHeight, new double[] { 29.5, 59, 86.9, 119 });
170      AddToReferenceAlgorithmValuesDict(referenceValues, 4, SortingMethod.ClusteredHeightArea, new double[] { 29.5, 59, 86.9, 118.9 });
171
172      AddToReferenceAlgorithmValuesDict(referenceValues, 5, SortingMethod.Given, new double[] { 10.1, 18.1, 24.4, 32.5 });
173      AddToReferenceAlgorithmValuesDict(referenceValues, 5, SortingMethod.HeightVolume, new double[] { 9, 16.7, 22.9, 30.7});
174      AddToReferenceAlgorithmValuesDict(referenceValues, 5, SortingMethod.VolumeHeight, new double[] { 10, 17.8, 24.5, 32.6 });
175      AddToReferenceAlgorithmValuesDict(referenceValues, 5, SortingMethod.AreaHeight, new double[] { 9.2, 16.1, 21.9, 29.5 });
176      AddToReferenceAlgorithmValuesDict(referenceValues, 5, SortingMethod.HeightArea, new double[] { 9, 16.6, 22.6, 30.5 });
177      AddToReferenceAlgorithmValuesDict(referenceValues, 5, SortingMethod.ClusteredAreaHeight, new double[] { 8.5, 15.7, 21, 28.5 });
178      AddToReferenceAlgorithmValuesDict(referenceValues, 5, SortingMethod.ClusteredHeightArea, new double[] { 8.4, 15.4, 21.1, 28.2});
179
180      AddToReferenceAlgorithmValuesDict(referenceValues, 6, SortingMethod.Given, new double[] { 11.7, 21.7, 33, 44.4});
181      AddToReferenceAlgorithmValuesDict(referenceValues, 6, SortingMethod.HeightVolume, new double[] { 10.9, 21.2, 31.8, 41.5 });
182      AddToReferenceAlgorithmValuesDict(referenceValues, 6, SortingMethod.VolumeHeight, new double[] { 11.7, 22, 34.2, 44 });
183      AddToReferenceAlgorithmValuesDict(referenceValues, 6, SortingMethod.AreaHeight, new double[] { 10.6, 20.2, 30.8, 39.5});
184      AddToReferenceAlgorithmValuesDict(referenceValues, 6, SortingMethod.HeightArea, new double[] { 10.9, 20.5, 31, 39.8 });
185      AddToReferenceAlgorithmValuesDict(referenceValues, 6, SortingMethod.ClusteredAreaHeight, new double[] { 10.2, 19.6, 29.9, 38.6 });
186      AddToReferenceAlgorithmValuesDict(referenceValues, 6, SortingMethod.ClusteredHeightArea, new double[] { 10.1, 19.8, 30.2, 38.8 });
187
188      AddToReferenceAlgorithmValuesDict(referenceValues, 7, SortingMethod.Given, new double[] { 9.4, 15.9, 19.3, 30 });
189      AddToReferenceAlgorithmValuesDict(referenceValues, 7, SortingMethod.HeightVolume, new double[] { 8.2, 14.6, 19.2, 28.1 });
190      AddToReferenceAlgorithmValuesDict(referenceValues, 7, SortingMethod.VolumeHeight, new double[] { 9.3, 15.6, 19.7, 30.2 });
191      AddToReferenceAlgorithmValuesDict(referenceValues, 7, SortingMethod.AreaHeight, new double[] { 8.1, 14.1, 18.2, 26.2 });
192      AddToReferenceAlgorithmValuesDict(referenceValues, 7, SortingMethod.HeightArea, new double[] { 8.1, 14.1, 18.9, 27,2 });
193      AddToReferenceAlgorithmValuesDict(referenceValues, 7, SortingMethod.ClusteredAreaHeight, new double[] { 7.6, 13.4, 16.9, 25 });
194      AddToReferenceAlgorithmValuesDict(referenceValues, 7, SortingMethod.ClusteredHeightArea, new double[] { 7.7, 13.3, 16.9, 24.9 });
195
196      AddToReferenceAlgorithmValuesDict(referenceValues, 8, SortingMethod.Given, new double[] { 11.6, 22, 28.5, 35.4 });
197      AddToReferenceAlgorithmValuesDict(referenceValues, 8, SortingMethod.HeightVolume, new double[] { 10.5, 20.9, 27.4, 33.9 });
198      AddToReferenceAlgorithmValuesDict(referenceValues, 8, SortingMethod.VolumeHeight, new double[] { 11.6, 22.1, 28.4, 35.4});
199      AddToReferenceAlgorithmValuesDict(referenceValues, 8, SortingMethod.AreaHeight, new double[] { 10.1, 20.3, 26.4, 32.2 });
200      AddToReferenceAlgorithmValuesDict(referenceValues, 8, SortingMethod.HeightArea, new double[] { 10.5, 20.8, 37.7, 33.9 });
201      AddToReferenceAlgorithmValuesDict(referenceValues, 8, SortingMethod.ClusteredAreaHeight, new double[] { 9.6, 19.4, 25.4, 31.4 });
202      AddToReferenceAlgorithmValuesDict(referenceValues, 8, SortingMethod.ClusteredHeightArea, new double[] { 9.5, 19.7, 25.5, 31.5 });
203
204      return referenceValues;
205    }
206
207    private void AddToReferenceAlgorithmValuesDict(Dictionary<Tuple<int, int, SortingMethod>, double> referenceValues, int @class, SortingMethod sortingMethod, double[] values) {
208      for (int i = 0; i < values.Length; i++) {
209        referenceValues.Add(new Tuple<int, int, SortingMethod>(@class, 50 + (50 * i), sortingMethod), values[i]);
210      }
211     
212    }
213
214
215    #endregion
216  }
217
218}
Note: See TracBrowser for help on using the repository browser.