Free cookie consent management tool by TermsFeed Policy Generator

Changeset 15424


Ignore:
Timestamp:
10/18/17 10:54:23 (7 years ago)
Author:
rhanghof
Message:

#2817:

  • Added some comments and regions to the source code
  • Addes reference instance files created by the test algoritm of S. Martello, D. Pisinger, D. Vigo
Location:
branches/2817-BinPackingSpeedup
Files:
321 added
3 edited

Legend:

Unmodified
Added
Removed

  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/BinPacking3D.cs

    r15308 r15424  
    203203    }
    204204
     205    #region Projections
     206       
    205207    private Vector3D ProjectBackward(Vector3D pos) {
    206208      var line = new Line3D(pos, new Vector3D(0, 0, -1));
    … …  
    262264                  .MinItems(x => x.Y).First();
    263265    }
    264 
     266    #endregion
     267
     268    #region Get items
     269
     270   
    265271    private IEnumerable<Tuple<PackingPosition, PackingItem>> GetItemsAbove(PackingPosition pos) {
    266272      var line = new Line3D(pos, new Vector3D(0, 1, 0));
    … …  
    292298        .Select(x => Tuple.Create(x.Position, x.Item));
    293299    }
     300    #endregion
    294301
    295302    public override PackingPosition FindExtremePointForItem(PackingItem item, bool rotated, bool stackingConstraints) {
    … …  
    316323    }
    317324
     325    #region Sliding based packing   
    318326    public override PackingPosition FindPositionBySliding(PackingItem item, bool rotated, bool stackingConstraints) {
    319327      //Starting-position at upper right corner (=left bottom point of item-rectangle is at position item.width,item.height)
    … …  
    365373      }
    366374    }
     375    #endregion
    367376    public override void ExtremePointBasedPacking(ref IList<int> sequence, IList<PackingItem> items, bool stackingConstraints) {
    368377      var temp = new List<int>(sequence);

  • branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/RandomInstanceProviderWithSRand.cs

    r15423 r15424  
    9999    /// Number of created test items. This items are used for packing them into the bin
    100100    /// </summary>
    101     private static readonly int[] numberOfGeneratedTestItems = new int[] { 10, 15, 20, 25, 30, 35, 40, 45, 50, 60, 70, 80, 90, 100, 150, 200 };   
     101    //private static readonly int[] numberOfGeneratedTestItems = new int[] { 10, 15, 20, 25, 30, 35, 40, 45, 50, 60, 70, 80, 90, 100, 150, 200 };
     102    private static readonly int[] numberOfGeneratedTestItems = new int[] { 50, 100, 150, 200 };
    102103
    103104    /// <summary>
    104105    /// Number of instance for which should be created for each instance
    105106    /// </summary>
    106     private static readonly int numberOfGeneratedInstances = 30;
     107    private static readonly int numberOfGeneratedInstances = 10;
    107108
    108109    #region Random Generator srand48

  • branches/2817-BinPackingSpeedup/HeuristicLab.Tests/HeuristicLab.Problems.Bin-Packing-3.3/AlgorithmTest.cs

    r15423 r15424  
    2828    [TestCategory("Problems.BinPacking")]
    2929    public void TestRandomInstanceProvider() {
    30      
     30
    3131      var referenceItemLists = ReadReferenceItemLists();
    3232      TestRandomInstanceProviderByClass(new RandomInstanceClass1ProviderWithSRand(), referenceItemLists);
    … …  
    3838      TestRandomInstanceProviderByClass(new RandomInstanceClass7ProviderWithSRand(), referenceItemLists);
    3939      TestRandomInstanceProviderByClass(new RandomInstanceClass8ProviderWithSRand(), referenceItemLists);
    40      
     40
    4141    }
    4242
    4343    private IDictionary<string, List<Dimension>> ReadReferenceItemLists() {
    4444      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
     45      string path = @".\..\HeuristicLab.Tests\HeuristicLab.Problems.Bin-Packing-3.3\ReferenceInstances";
    4646
    4747      string[] files = Directory.GetFiles(path);
    … …  
    102102    /// <summary>
    103103    /// Constants for testing the algorithm
    104     /// The test parameter are defined in the paper
     104    /// The test parameters are defined in the paper
    105105    /// </summary>
    106106    private const int NUMBER_OF_TEST_INSTANCES = 10;
    … …  
    110110    [TestMethod]
    111111    [TestCategory("Problems.BinPacking")]
    112     public void TestExtremePointAlgorithm() {
    113       TestExtremePointAlgorithmByParameters(new RandomInstanceClass1ProviderWithSRand(), 1, SortingMethod.Given, FittingMethod.FirstFit);
    114 
    115 
    116     }
     112    public void TestExtremePointAlgorithmClass1() {
     113      TestExtremePointAlgorithm(new RandomInstanceClass1ProviderWithSRand(), 1);
     114    }
     115
     116    [TestMethod]
     117    [TestCategory("Problems.BinPacking")]
     118    public void TestExtremePointAlgorithmClass2() {
     119      TestExtremePointAlgorithm(new RandomInstanceClass2ProviderWithSRand(), 2);
     120    }
     121
     122    [TestMethod]
     123    [TestCategory("Problems.BinPacking")]
     124    public void TestExtremePointAlgorithmClass3() {
     125      TestExtremePointAlgorithm(new RandomInstanceClass3ProviderWithSRand(), 3);
     126    }
     127
     128    [TestMethod]
     129    [TestCategory("Problems.BinPacking")]
     130    public void TestExtremePointAlgorithmClass4() {
     131      TestExtremePointAlgorithm(new RandomInstanceClass4ProviderWithSRand(), 4);
     132    }
     133
     134    [TestMethod]
     135    [TestCategory("Problems.BinPacking")]
     136    public void TestExtremePointAlgorithmClass5() {
     137      TestExtremePointAlgorithm(new RandomInstanceClass5ProviderWithSRand(), 5);
     138    }
     139
     140    [TestMethod]
     141    [TestCategory("Problems.BinPacking")]
     142    public void TestExtremePointAlgorithmClass6() {
     143      TestExtremePointAlgorithm(new RandomInstanceClass6ProviderWithSRand(), 6);
     144    }
     145
     146    [TestMethod]
     147    [TestCategory("Problems.BinPacking")]
     148    public void TestExtremePointAlgorithmClass7() {
     149      TestExtremePointAlgorithm(new RandomInstanceClass7ProviderWithSRand(), 7);
     150    }
     151
     152    [TestMethod]
     153    [TestCategory("Problems.BinPacking")]
     154    public void TestExtremePointAlgorithmClass8() {
     155      TestExtremePointAlgorithm(new RandomInstanceClass8ProviderWithSRand(), 8);
     156    }
     157
     158    private void TestExtremePointAlgorithm(RandomInstanceProviderWithSRand randomInstanceProvider, int @class) {
     159      foreach (SortingMethod sortingMethod in Enum.GetValues(typeof(SortingMethod))) {
     160        //foreach (FittingMethod fittingMethod in Enum.GetValues(typeof(FittingMethod))) {
     161        FittingMethod fittingMethod = FittingMethod.FirstFit;
     162        TestExtremePointAlgorithmByParameters(randomInstanceProvider, @class, sortingMethod, fittingMethod);
     163        //}
     164      }
     165    }
     166
     167
     168
    117169
    118170    private void TestExtremePointAlgorithmByParameters(RandomInstanceProviderWithSRand randomInstanceProvider, int @class, SortingMethod sortingMethod, FittingMethod fittingMethod) {
    … …  
    146198
    147199        double referenceValue = 0.0;
    148        
     200
    149201        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);
     202          Console.WriteLine($"{numItems}-{@class}-{sortingMethod}: \t{referenceValue} \t {(double)sumNumberOfBins / (double)NUMBER_OF_TEST_INSTANCES} \t{(referenceValue - ((double)sumNumberOfBins / (double)NUMBER_OF_TEST_INSTANCES)):F2}");
     203          Assert.AreEqual(referenceValue, (double)sumNumberOfBins / (double)NUMBER_OF_TEST_INSTANCES, 10.0);
    152204        }
    153205      }
    … …  
    157209    /// <summary>
    158210    /// Returns a dictionary which contains the reference values from table 2 given by the paper https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2007-41.pdf
     211    /// Dictionary<Tuple<int, int, SortingMethod>, double> -> Dictionary<Tuple<@class, number of items, SortingMethod>, value>
    159212    /// </summary>
    160213    /// <returns></returns>
    … …  
    162215      Dictionary<Tuple<int, int, SortingMethod>, double> referenceValues = new Dictionary<Tuple<int, int, SortingMethod>, double>();
    163216
    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 
     217      AddToReferenceAlgorithmValuesDict(referenceValues, 1, SortingMethod.Given, new double[] { 14.6, 29.2, 40.1, 55.9});
     218      AddToReferenceAlgorithmValuesDict(referenceValues, 1, SortingMethod.HeightVolume, new double[] { 15, 29.2, 39.9, 55.6 });
     219      AddToReferenceAlgorithmValuesDict(referenceValues, 1, SortingMethod.VolumeHeight, new double[] { 14.4, 29.5, 40.3, 55.7 });
     220      AddToReferenceAlgorithmValuesDict(referenceValues, 1, SortingMethod.AreaHeight, new double[] { 14.4, 28.3, 39.2, 53.2 });
     221      AddToReferenceAlgorithmValuesDict(referenceValues, 1, SortingMethod.HeightArea, new double[] { 15, 29, 39.8, 55.1});
     222
     223      AddToReferenceAlgorithmValuesDict(referenceValues, 4, SortingMethod.Given, new double[] { 29.7, 60.2, 88.5, 119.9 });
     224      AddToReferenceAlgorithmValuesDict(referenceValues, 4, SortingMethod.HeightVolume, new double[] { 30.1, 59.6, 88.3, 120.1 });
     225      AddToReferenceAlgorithmValuesDict(referenceValues, 4, SortingMethod.VolumeHeight, new double[] { 29.9, 60.4, 88.6, 119.6 });
     226      AddToReferenceAlgorithmValuesDict(referenceValues, 4, SortingMethod.AreaHeight, new double[] { 30, 59.7, 88.4, 120.3 });
     227      AddToReferenceAlgorithmValuesDict(referenceValues, 4, SortingMethod.HeightArea, new double[] { 30, 59.6, 88.3, 120 });
     228
     229      AddToReferenceAlgorithmValuesDict(referenceValues, 5, SortingMethod.Given, new double[] { 10.1, 18.1, 24.4, 32.5 });
     230      AddToReferenceAlgorithmValuesDict(referenceValues, 5, SortingMethod.HeightVolume, new double[] { 9, 16.7, 22.9, 30.7});
     231      AddToReferenceAlgorithmValuesDict(referenceValues, 5, SortingMethod.VolumeHeight, new double[] { 10, 17.8, 24.5, 32.6 });
     232      AddToReferenceAlgorithmValuesDict(referenceValues, 5, SortingMethod.AreaHeight, new double[] { 9.2, 16.1, 21.9, 29.5 });
     233      AddToReferenceAlgorithmValuesDict(referenceValues, 5, SortingMethod.HeightArea, new double[] { 9, 16.6, 22.6, 30.5 });
     234
     235      AddToReferenceAlgorithmValuesDict(referenceValues, 6, SortingMethod.Given, new double[] { 11.7, 21.7, 33, 44.4});
     236      AddToReferenceAlgorithmValuesDict(referenceValues, 6, SortingMethod.HeightVolume, new double[] { 10.9, 21.2, 31.8, 41.5 });
     237      AddToReferenceAlgorithmValuesDict(referenceValues, 6, SortingMethod.VolumeHeight, new double[] { 11.7, 22, 34.2, 44 });
     238      AddToReferenceAlgorithmValuesDict(referenceValues, 6, SortingMethod.AreaHeight, new double[] { 10.6, 20.2, 30.8, 39.5});
     239      AddToReferenceAlgorithmValuesDict(referenceValues, 6, SortingMethod.HeightArea, new double[] { 10.9, 20.5, 31, 39.8 });
     240
     241      AddToReferenceAlgorithmValuesDict(referenceValues, 7, SortingMethod.Given, new double[] { 9.4, 15.9, 19.3, 30 });
     242      AddToReferenceAlgorithmValuesDict(referenceValues, 7, SortingMethod.HeightVolume, new double[] { 8.2, 14.6, 19.2, 28.1 });
     243      AddToReferenceAlgorithmValuesDict(referenceValues, 7, SortingMethod.VolumeHeight, new double[] { 9.3, 15.6, 19.7, 30.2 });
     244      AddToReferenceAlgorithmValuesDict(referenceValues, 7, SortingMethod.AreaHeight, new double[] { 8.1, 14.1, 18.2, 26.2 });
     245      AddToReferenceAlgorithmValuesDict(referenceValues, 7, SortingMethod.HeightArea, new double[] { 8.1, 14.1, 18.9, 27,2 });
     246
     247      AddToReferenceAlgorithmValuesDict(referenceValues, 8, SortingMethod.Given, new double[] { 11.6, 22, 28.5, 35.4 });
     248      AddToReferenceAlgorithmValuesDict(referenceValues, 8, SortingMethod.HeightVolume, new double[] { 10.5, 20.9, 27.4, 33.9 });
     249      AddToReferenceAlgorithmValuesDict(referenceValues, 8, SortingMethod.VolumeHeight, new double[] { 11.6, 22.1, 28.4, 35.4});
     250      AddToReferenceAlgorithmValuesDict(referenceValues, 8, SortingMethod.AreaHeight, new double[] { 10.1, 20.3, 26.4, 32.2 });
     251      AddToReferenceAlgorithmValuesDict(referenceValues, 8, SortingMethod.HeightArea, new double[] { 10.5, 20.8, 37.7, 33.9 });
    192252      return referenceValues;
     253    }
     254
     255    private void AddToReferenceAlgorithmValuesDict(Dictionary<Tuple<int, int, SortingMethod>, double> referenceValues, int @class, SortingMethod sortingMethod, double[] values) {
     256      for (int i = 0; i < values.Length; i++) {
     257        referenceValues.Add(new Tuple<int, int, SortingMethod>(@class, 50 + (50 * i), sortingMethod), values[i]);
     258      }
     259     
    193260    }
    194261
Note: See TracChangeset for help on using the changeset viewer.