Changeset 15959
- Timestamp:
- 06/13/18 15:32:27 (7 years ago)
- Location:
- branches/2817-BinPackingSpeedup
- Files:
-
- 1 added
- 1 deleted
- 7 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Algorithms/ExtremePointAlgorithm.cs
r15838 r15959 40 40 41 41 public enum SortingMethod { All, Given, VolumeHeight, HeightVolume, AreaHeight, HeightArea, ClusteredAreaHeight, ClusteredHeightArea } 42 public enum FittingMethod { All, FirstFit, ResidualSpaceBestFit, FreeVolumeBestFit, MinimumResidualSpaceLeft, FormClosure}42 public enum FittingMethod { All, FirstFit, ResidualSpaceBestFit, FreeVolumeBestFit, MinimumResidualSpaceLeft, WidthBestFit } 43 43 44 44 public enum ExtremePointCreationMethod { All, PointProjection, LineProjection } -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Packer/BinPackerFactory.cs
r15731 r15959 53 53 binPacker = new BinPackerMinRSLeft(); 54 54 break; 55 case FittingMethod. FormClosure:56 binPacker = new BinPacker FormClosure();55 case FittingMethod.WidthBestFit: 56 binPacker = new BinPackerWidthBestFit(); 57 57 break; 58 58 default: -
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj
r15731 r15959 128 128 <Compile Include="3D\Packer\BinPackerFreeVolumeBestFit.cs" /> 129 129 <Compile Include="3D\Packer\BinPackerMinRSLeft.cs" /> 130 <Compile Include="3D\Packer\BinPacker FormClosure.cs" />130 <Compile Include="3D\Packer\BinPackerWidthBestFit.cs" /> 131 131 <Compile Include="3D\Packer\BinPackerResidualSpaceBestFit.cs" /> 132 132 <Compile Include="3D\Instances\ThreeDInstanceDescriptor.cs" /> -
branches/2817-BinPackingSpeedup/HeuristicLab.Tests/HeuristicLab.Problems.Bin-Packing-3.3/3D/Algorithms/ExtremePointAlgorithmTest.cs
r15585 r15959 25 25 _items = new List<PackingItem>(); 26 26 27 _items.Add(new PackingItem(8, 10, 10, _packingShape1, 1000, 1 )); // 0, V = 800, A = 80, h = 1028 _items.Add(new PackingItem(10, 8, 10, _packingShape1, 1000, 2 )); // 1, V = 800, A = 100, h = 829 _items.Add(new PackingItem(10, 10, 8, _packingShape1, 1000, 3 )); // 2, V = 800, A = 80, h = 1030 _items.Add(new PackingItem(8, 8, 10, _packingShape1, 1000, 4 )); // 3, V = 640, A = 80, h = 831 _items.Add(new PackingItem(10, 8, 8, _packingShape1, 1000, 0 )); // 4, V = 640, A = 80, h = 832 _items.Add(new PackingItem(8, 10, 8, _packingShape1, 1000, 1 )); // 5, V = 640, A = 64, h = 1033 _items.Add(new PackingItem(8, 8, 8, _packingShape1, 1000, 2 )); // 6, V = 512, A = 64, h = 827 _items.Add(new PackingItem(8, 10, 10, _packingShape1, 1000, 1, 1)); // 0, V = 800, A = 80, h = 10 28 _items.Add(new PackingItem(10, 8, 10, _packingShape1, 1000, 2, 1)); // 1, V = 800, A = 100, h = 8 29 _items.Add(new PackingItem(10, 10, 8, _packingShape1, 1000, 3, 1)); // 2, V = 800, A = 80, h = 10 30 _items.Add(new PackingItem(8, 8, 10, _packingShape1, 1000, 4, 1)); // 3, V = 640, A = 80, h = 8 31 _items.Add(new PackingItem(10, 8, 8, _packingShape1, 1000, 0, 1)); // 4, V = 640, A = 80, h = 8 32 _items.Add(new PackingItem(8, 10, 8, _packingShape1, 1000, 1, 1)); // 5, V = 640, A = 64, h = 10 33 _items.Add(new PackingItem(8, 8, 8, _packingShape1, 1000, 2, 1)); // 6, V = 512, A = 64, h = 8 34 34 35 _items.Add(new PackingItem(10, 10, 10, _packingShape1, 1000, 3 )); // 7, V = 1000, A = 100, h = 1035 _items.Add(new PackingItem(10, 10, 10, _packingShape1, 1000, 3, 1)); // 7, V = 1000, A = 100, h = 10 36 36 37 _items.Add(new PackingItem(9, 10, 10, _packingShape1, 1000, 4 )); // 8, V = 900, A = 90, h = 1038 _items.Add(new PackingItem(10, 9, 10, _packingShape1, 1000, 0 )); // 9, V = 900, A = 100, h = 939 _items.Add(new PackingItem(10, 10, 9, _packingShape1, 1000, 1 )); // 10, V = 900, A = 90, h = 1040 _items.Add(new PackingItem(9, 9, 10, _packingShape1, 1000, 2 )); // 11, V = 810, A = 90, h = 941 _items.Add(new PackingItem(10, 9, 9, _packingShape1, 1000, 3 )); // 12, V = 810, A = 90, h = 942 _items.Add(new PackingItem(9, 10, 9, _packingShape1, 1000, 4 )); // 13, V = 810, A = 81, h = 1043 _items.Add(new PackingItem(9, 9, 9, _packingShape1, 1000, 0 )); // 14, V = 729, A = 81, h = 937 _items.Add(new PackingItem(9, 10, 10, _packingShape1, 1000, 4, 1)); // 8, V = 900, A = 90, h = 10 38 _items.Add(new PackingItem(10, 9, 10, _packingShape1, 1000, 0, 1)); // 9, V = 900, A = 100, h = 9 39 _items.Add(new PackingItem(10, 10, 9, _packingShape1, 1000, 1, 1)); // 10, V = 900, A = 90, h = 10 40 _items.Add(new PackingItem(9, 9, 10, _packingShape1, 1000, 2, 1)); // 11, V = 810, A = 90, h = 9 41 _items.Add(new PackingItem(10, 9, 9, _packingShape1, 1000, 3, 1)); // 12, V = 810, A = 90, h = 9 42 _items.Add(new PackingItem(9, 10, 9, _packingShape1, 1000, 4, 1)); // 13, V = 810, A = 81, h = 10 43 _items.Add(new PackingItem(9, 9, 9, _packingShape1, 1000, 0, 1)); // 14, V = 729, A = 81, h = 9 44 44 45 45 _extremPointAlgorithm = new ExtremePointAlgorithm(); -
branches/2817-BinPackingSpeedup/HeuristicLab.Tests/HeuristicLab.Problems.Bin-Packing-3.3/3D/Instances/RandomInstanceProviderTest.cs
r15585 r15959 169 169 foreach (SortingMethod sortingMethod in Enum.GetValues(typeof(SortingMethod))) { 170 170 //foreach (FittingMethod fittingMethod in Enum.GetValues(typeof(FittingMethod))) { 171 FittingMethod fittingMethod = FittingMethod.FirstFit; 172 foreach (ExtremePointCreationMethod epCreationMethod in Enum.GetValues(typeof(ExtremePointCreationMethod))) { 171 FittingMethod fittingMethod = FittingMethod.FreeVolumeBestFit; 172 TestExtremePointAlgorithmByParameters(randomInstanceProvider, @class, sortingMethod, fittingMethod, ExtremePointCreationMethod.LineProjection); 173 174 /*foreach (ExtremePointCreationMethod epCreationMethod in Enum.GetValues(typeof(ExtremePointCreationMethod))) { 173 175 TestExtremePointAlgorithmByParameters(randomInstanceProvider, @class, sortingMethod, fittingMethod, epCreationMethod); 174 } 175 176 }*/ 177 176 178 //} 177 179 } … … 183 185 foreach (var numItems in NUMBER_OF_TEST_ITEMS) { 184 186 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; 187 188 double referenceValue = 0.0; 189 if (referenceValues.TryGetValue(new Tuple<int, int, SortingMethod>(@class, numItems, sortingMethod), out referenceValue)) { 190 for (int instance = 1; instance <= NUMBER_OF_TEST_INSTANCES; instance++) { 191 string name = string.Format("n={0}-id={1:00} (class={2})", numItems, instance, @class); 192 var selectedDataDescriptor = dataDescriptors.Where(dataDescriptor => dataDescriptor.Name == name); 193 Assert.IsNotNull(selectedDataDescriptor?.First()); 194 var packingData = randomInstanceProvider.LoadData(selectedDataDescriptor.First()); 195 196 ExtremePointAlgorithm algorithm = new ExtremePointAlgorithm(); 197 algorithm.SortingMethodParameter.Value.Value = sortingMethod; 198 algorithm.FittingMethodParameter.Value.Value = fittingMethod; 199 algorithm.ExtremePointCreationMethodParameter.Value.Value = epCreationMethod; 200 algorithm.SortByMaterialParameter.Value.Value = false; 201 202 algorithm.Problem.UseStackingConstraintsParameter.Value.Value = false; 203 algorithm.Problem.Load(packingData); 204 205 algorithm.Start(); 206 207 PackingPlan<BinPacking3D.PackingPosition, PackingShape, PackingItem> bestPackingPlan = null; 208 foreach (Optimization.IResult result in algorithm.Results) { 209 if (result.Name == "Best Solution") { 210 bestPackingPlan = (PackingPlan<BinPacking3D.PackingPosition, PackingShape, PackingItem>)result.Value; 211 break; 212 } 204 213 } 214 215 sumNumberOfBins += bestPackingPlan.NrOfBins; 205 216 } 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); 217 218 //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};"); 219 var implementation = (double)sumNumberOfBins / (double)NUMBER_OF_TEST_INSTANCES; 220 var enhancement = (referenceValue * 100 / implementation) - 100; 221 Console.WriteLine($"{@class};{numItems};{sortingMethod};{enhancement:F2} %;{referenceValue};{implementation}"); 222 // 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}"); 223 //Assert.AreEqual(referenceValue, (double)sumNumberOfBins / (double)NUMBER_OF_TEST_INSTANCES, 20.0); 215 224 } 216 225 } -
branches/2817-BinPackingSpeedup/HeuristicLab.Tests/HeuristicLab.Problems.Bin-Packing-3.3/3D/Instances/ThreeDInstanceParserTest.cs
r15731 r15959 18 18 _items1 = new List<PackingItem>(); 19 19 20 _items1.Add(new PackingItem(8, 10, 10, _packingShape, 800, 1 )); // 0, V = 800, A = 80, h = 1021 _items1.Add(new PackingItem(10, 8, 10, _packingShape, 800, 2 )); // 1, V = 800, A = 100, h = 822 _items1.Add(new PackingItem(10, 10, 8, _packingShape, 800, 3 )); // 2, V = 800, A = 80, h = 1023 _items1.Add(new PackingItem(8, 8, 10, _packingShape, 640, 4 )); // 3, V = 640, A = 80, h = 824 _items1.Add(new PackingItem(10, 8, 8, _packingShape, 640, 0 )); // 4, V = 640, A = 80, h = 825 _items1.Add(new PackingItem(8, 10, 8, _packingShape, 640, 1 )); // 5, V = 640, A = 64, h = 1026 _items1.Add(new PackingItem(8, 8, 8, _packingShape, 512, 2 )); // 6, V = 512, A = 64, h = 820 _items1.Add(new PackingItem(8, 10, 10, _packingShape, 800, 1, 1)); // 0, V = 800, A = 80, h = 10 21 _items1.Add(new PackingItem(10, 8, 10, _packingShape, 800, 2, 1)); // 1, V = 800, A = 100, h = 8 22 _items1.Add(new PackingItem(10, 10, 8, _packingShape, 800, 3, 1)); // 2, V = 800, A = 80, h = 10 23 _items1.Add(new PackingItem(8, 8, 10, _packingShape, 640, 4, 1)); // 3, V = 640, A = 80, h = 8 24 _items1.Add(new PackingItem(10, 8, 8, _packingShape, 640, 0, 1)); // 4, V = 640, A = 80, h = 8 25 _items1.Add(new PackingItem(8, 10, 8, _packingShape, 640, 1, 1)); // 5, V = 640, A = 64, h = 10 26 _items1.Add(new PackingItem(8, 8, 8, _packingShape, 512, 2, 1)); // 6, V = 512, A = 64, h = 8 27 27 28 _items1.Add(new PackingItem(10, 10, 10, _packingShape,1000,3 )); // 7, V = 1000, A = 100, h = 1028 _items1.Add(new PackingItem(10, 10, 10, _packingShape,1000,3, 1)); // 7, V = 1000, A = 100, h = 10 29 29 30 _items1.Add(new PackingItem(9, 10, 10, _packingShape, 900, 4 )); // 8, V = 900, A = 90, h = 1031 _items1.Add(new PackingItem(10, 9, 10, _packingShape, 900, 0 )); // 9, V = 900, A = 100, h = 932 _items1.Add(new PackingItem(10, 10, 9, _packingShape, 900, 1 )); // 10, V = 900, A = 90, h = 1033 _items1.Add(new PackingItem(9, 9, 10, _packingShape, 810, 2 )); // 11, V = 810, A = 90, h = 934 _items1.Add(new PackingItem(10, 9, 9, _packingShape, 810, 3 )); // 12, V = 810, A = 90, h = 935 _items1.Add(new PackingItem(9, 10, 9, _packingShape, 810, 4 )); // 13, V = 810, A = 81, h = 1036 _items1.Add(new PackingItem(9, 9, 9, _packingShape, 729, 0 )); // 14, V = 729, A = 81, h = 930 _items1.Add(new PackingItem(9, 10, 10, _packingShape, 900, 4, 1)); // 8, V = 900, A = 90, h = 10 31 _items1.Add(new PackingItem(10, 9, 10, _packingShape, 900, 0, 1)); // 9, V = 900, A = 100, h = 9 32 _items1.Add(new PackingItem(10, 10, 9, _packingShape, 900, 1, 1)); // 10, V = 900, A = 90, h = 10 33 _items1.Add(new PackingItem(9, 9, 10, _packingShape, 810, 2, 1)); // 11, V = 810, A = 90, h = 9 34 _items1.Add(new PackingItem(10, 9, 9, _packingShape, 810, 3, 1)); // 12, V = 810, A = 90, h = 9 35 _items1.Add(new PackingItem(9, 10, 9, _packingShape, 810, 4, 1)); // 13, V = 810, A = 81, h = 10 36 _items1.Add(new PackingItem(9, 9, 9, _packingShape, 729, 0, 1)); // 14, V = 729, A = 81, h = 9 37 37 38 38 _items2 = new List<PackingItem>(); 39 _items2.Add(new PackingItem(8, 10, 10, _packingShape, 800, 1 )); // 0, V = 800, A = 80, h = 1040 _items2.Add(new PackingItem(10, 8, 10, _packingShape, 800, 2 )); // 1, V = 800, A = 100, h = 841 _items2.Add(new PackingItem(10, 10, 8, _packingShape, 800, 3 )); // 2, V = 800, A = 80, h = 1042 _items2.Add(new PackingItem(8, 8, 10, _packingShape, 640, 4 )); // 3, V = 640, A = 80, h = 843 _items2.Add(new PackingItem(10, 8, 8, _packingShape, 640, 0 )); // 4, V = 640, A = 80, h = 844 _items2.Add(new PackingItem(8, 10, 8, _packingShape, 640, 1 )); // 5, V = 640, A = 64, h = 1039 _items2.Add(new PackingItem(8, 10, 10, _packingShape, 800, 1, 1)); // 0, V = 800, A = 80, h = 10 40 _items2.Add(new PackingItem(10, 8, 10, _packingShape, 800, 2, 1)); // 1, V = 800, A = 100, h = 8 41 _items2.Add(new PackingItem(10, 10, 8, _packingShape, 800, 3, 1)); // 2, V = 800, A = 80, h = 10 42 _items2.Add(new PackingItem(8, 8, 10, _packingShape, 640, 4, 1)); // 3, V = 640, A = 80, h = 8 43 _items2.Add(new PackingItem(10, 8, 8, _packingShape, 640, 0, 1)); // 4, V = 640, A = 80, h = 8 44 _items2.Add(new PackingItem(8, 10, 8, _packingShape, 640, 1, 1)); // 5, V = 640, A = 64, h = 10 45 45 } 46 46 -
branches/2817-BinPackingSpeedup/HeuristicLab.Tests/HeuristicLab.Problems.Bin-Packing-3.3/3D/Sorting/PermutationSortingTest.cs
r15554 r15959 17 17 _items = new List<PackingItem>(); 18 18 19 _items.Add(new PackingItem(8, 10, 10, _packingShape, 1000, 1 )); // 0, V = 800, A = 80, h = 1020 _items.Add(new PackingItem(10, 8, 10, _packingShape, 1000, 2 )); // 1, V = 800, A = 100, h = 821 _items.Add(new PackingItem(10, 10, 8, _packingShape, 1000, 3 )); // 2, V = 800, A = 80, h = 1022 _items.Add(new PackingItem(8, 8, 10, _packingShape, 1000, 4 )); // 3, V = 640, A = 80, h = 823 _items.Add(new PackingItem(10, 8, 8, _packingShape, 1000, 0 )); // 4, V = 640, A = 80, h = 824 _items.Add(new PackingItem(8, 10, 8, _packingShape, 1000, 1 )); // 5, V = 640, A = 64, h = 1025 _items.Add(new PackingItem(8, 8, 8, _packingShape, 1000, 2 )); // 6, V = 512, A = 64, h = 819 _items.Add(new PackingItem(8, 10, 10, _packingShape, 1000, 1, 1)); // 0, V = 800, A = 80, h = 10 20 _items.Add(new PackingItem(10, 8, 10, _packingShape, 1000, 2, 1)); // 1, V = 800, A = 100, h = 8 21 _items.Add(new PackingItem(10, 10, 8, _packingShape, 1000, 3, 1)); // 2, V = 800, A = 80, h = 10 22 _items.Add(new PackingItem(8, 8, 10, _packingShape, 1000, 4, 1)); // 3, V = 640, A = 80, h = 8 23 _items.Add(new PackingItem(10, 8, 8, _packingShape, 1000, 0, 1)); // 4, V = 640, A = 80, h = 8 24 _items.Add(new PackingItem(8, 10, 8, _packingShape, 1000, 1, 1)); // 5, V = 640, A = 64, h = 10 25 _items.Add(new PackingItem(8, 8, 8, _packingShape, 1000, 2, 1)); // 6, V = 512, A = 64, h = 8 26 26 27 _items.Add(new PackingItem(10, 10, 10, _packingShape, 1000, 3 )); // 7, V = 1000, A = 100, h = 1027 _items.Add(new PackingItem(10, 10, 10, _packingShape, 1000, 3, 1)); // 7, V = 1000, A = 100, h = 10 28 28 29 _items.Add(new PackingItem(9, 10, 10, _packingShape, 1000, 4 )); // 8, V = 900, A = 90, h = 1030 _items.Add(new PackingItem(10, 9, 10, _packingShape, 1000, 0 )); // 9, V = 900, A = 100, h = 931 _items.Add(new PackingItem(10, 10, 9, _packingShape, 1000, 1 )); // 10, V = 900, A = 90, h = 1032 _items.Add(new PackingItem(9, 9, 10, _packingShape, 1000, 2 )); // 11, V = 810, A = 90, h = 933 _items.Add(new PackingItem(10, 9, 9, _packingShape, 1000, 3 )); // 12, V = 810, A = 90, h = 934 _items.Add(new PackingItem(9, 10, 9, _packingShape, 1000, 4 )); // 13, V = 810, A = 81, h = 1035 _items.Add(new PackingItem(9, 9, 9, _packingShape, 1000, 0 )); // 14, V = 729, A = 81, h = 929 _items.Add(new PackingItem(9, 10, 10, _packingShape, 1000, 4, 1)); // 8, V = 900, A = 90, h = 10 30 _items.Add(new PackingItem(10, 9, 10, _packingShape, 1000, 0, 1)); // 9, V = 900, A = 100, h = 9 31 _items.Add(new PackingItem(10, 10, 9, _packingShape, 1000, 1, 1)); // 10, V = 900, A = 90, h = 10 32 _items.Add(new PackingItem(9, 9, 10, _packingShape, 1000, 2, 1)); // 11, V = 810, A = 90, h = 9 33 _items.Add(new PackingItem(10, 9, 9, _packingShape, 1000, 3, 1)); // 12, V = 810, A = 90, h = 9 34 _items.Add(new PackingItem(9, 10, 9, _packingShape, 1000, 4, 1)); // 13, V = 810, A = 81, h = 10 35 _items.Add(new PackingItem(9, 9, 9, _packingShape, 1000, 0, 1)); // 14, V = 729, A = 81, h = 9 36 36 } 37 37
Note: See TracChangeset
for help on using the changeset viewer.