Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
10/17/17 13:52:29 (7 years ago)
Author:
rhanghof
Message:

#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:
1 edited

Legend:

Unmodified
Added
Removed

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

    r15418 r15423  
    88
    99namespace HeuristicLab.Problems.BinPacking.Tests {
    10     [TestClass]
    11     public class AlgorithmTest {
     10  [TestClass]
     11  public class AlgorithmTest {
    1212
    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; }
     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;
    18145        }
    19146
    20         #region TestRandomInstanceProvider
     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    }
    21155
    22156
    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() {
     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);
    30188
    31189
    32             var referenceItemLists = ReadReferenceItemLists();
     190      var s = referenceValues[new Tuple<int, int, SortingMethod>(1, 200, SortingMethod.HeightArea)];
    33191
    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 = @"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
    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 parameter 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")]
    114         public void TestExtremePointAlgorithm() {
    115             TestExtremePointAlgorithmByParameters(new RandomInstanceClass1Provider(), 1, SortingMethod.Given, FittingMethod.FirstFit);
     192      return referenceValues;
     193    }
    116194
    117195
    118         }
    119 
    120         private void TestExtremePointAlgorithmByParameters(RandomInstanceProvider randomInstanceProvider, int @class, SortingMethod sortingMethod, FittingMethod fittingMethod) {
    121             var dataDescriptors = randomInstanceProvider.GetDataDescriptors();
    122             var referenceValues = GetReferenceAlgorithmValues();
    123             foreach (var numItems in NUMBER_OF_TEST_ITEMS) {
    124                 int sumNumberOfBins = 0;
    125                 for (int instance = 1; instance <= NUMBER_OF_TEST_INSTANCES; instance++) {
    126                     string name = string.Format("n={0}-id={1:00} (class={2})", numItems, instance, @class);
    127                     var selectedDataDescriptor = dataDescriptors.Where(dataDescriptor => dataDescriptor.Name == name);
    128                     Assert.IsNotNull(selectedDataDescriptor?.First());
    129                     var packingData = randomInstanceProvider.LoadData(selectedDataDescriptor.First());
    130 
    131                     ExtremePointAlgorithm algorithm = new ExtremePointAlgorithm();
    132                     algorithm.SortingMethodParameter.Value.Value = sortingMethod;
    133                     algorithm.FittingMethodParameter.Value.Value = fittingMethod;
    134                     algorithm.Problem.Load(packingData);
    135 
    136                     algorithm.Start();
    137 
    138                     PackingPlan<BinPacking3D.PackingPosition, PackingShape, PackingItem> bestPackingPlan = null;
    139                     foreach (Optimization.IResult result in algorithm.Results) {
    140                         if (result.Name == "Best Solution") {
    141                             bestPackingPlan = (PackingPlan<BinPacking3D.PackingPosition, PackingShape, PackingItem>)result.Value;
    142                             break;
    143                         }
    144                     }
    145 
    146                     sumNumberOfBins += bestPackingPlan.NrOfBins;
    147                 }
    148 
    149                 double referenceValue = 0.0;
    150                 if (referenceValues.TryGetValue(new Tuple<int, int, SortingMethod>(@class, numItems, sortingMethod), out referenceValue)) {
    151                     Assert.AreEqual(referenceValue, (double)sumNumberOfBins / (double)NUMBER_OF_TEST_INSTANCES, 0.1);
    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     }
     196    #endregion
     197  }
    198198
    199199}
Note: See TracChangeset for help on using the changeset viewer.