[15554] | 1 | using System;
|
---|
| 2 | using System.IO;
|
---|
| 3 | using Microsoft.VisualStudio.TestTools.UnitTesting;
|
---|
| 4 | using HeuristicLab.Problems.BinPacking3D;
|
---|
| 5 | using HeuristicLab.Problems.BinPacking3D.Instances;
|
---|
| 6 | using System.Collections.Generic;
|
---|
| 7 | using System.Linq;
|
---|
| 8 | using HeuristicLab.Core;
|
---|
| 9 |
|
---|
| 10 | namespace 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;
|
---|
[15585] | 172 | foreach (ExtremePointCreationMethod epCreationMethod in Enum.GetValues(typeof(ExtremePointCreationMethod))) {
|
---|
| 173 | TestExtremePointAlgorithmByParameters(randomInstanceProvider, @class, sortingMethod, fittingMethod, epCreationMethod);
|
---|
| 174 | }
|
---|
| 175 |
|
---|
[15554] | 176 | //}
|
---|
| 177 | }
|
---|
| 178 | }
|
---|
| 179 |
|
---|
[15585] | 180 | private void TestExtremePointAlgorithmByParameters(RandomInstanceProvider randomInstanceProvider, int @class, SortingMethod sortingMethod, FittingMethod fittingMethod, ExtremePointCreationMethod epCreationMethod) {
|
---|
[15554] | 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;
|
---|
[15585] | 194 | algorithm.ExtremePointCreationMethodParameter.Value.Value = epCreationMethod;
|
---|
[15554] | 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)) {
|
---|
[15585] | 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}");
|
---|
[15554] | 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 | }
|
---|