Free cookie consent management tool by TermsFeed Policy Generator

Changeset 15423


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.
Location:
branches/2817-BinPackingSpeedup
Files:
2 edited

Legend:

Unmodified
Added
Removed

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

    r15418 r15423  
    2626using System.IO;
    2727using System.Linq;
     28using System.Reflection;
    2829using HeuristicLab.Common;
    2930using HeuristicLab.Core;
    … …  
    3334namespace HeuristicLab.Problems.BinPacking3D {
    3435  // make sure that for each class we have a separate entry in the problem instance providers
     36 
    3537  public class RandomInstanceClass1ProviderWithSRand : RandomInstanceProviderWithSRand {
    3638    public RandomInstanceClass1ProviderWithSRand() : base() { @class = 1; binWidth = binHeight = binDepth = 100; }
    37   }
     39   
     40  }
     41
    3842  public class RandomInstanceClass2ProviderWithSRand : RandomInstanceProviderWithSRand {
    3943    public RandomInstanceClass2ProviderWithSRand() : base() { @class = 2; binWidth = binHeight = binDepth = 100; }
     44   
    4045  }
    4146  public class RandomInstanceClass3ProviderWithSRand : RandomInstanceProviderWithSRand {
    4247    public RandomInstanceClass3ProviderWithSRand() : base() { @class = 3; binWidth = binHeight = binDepth = 100; }
     48   
    4349  }
    4450  public class RandomInstanceClass4ProviderWithSRand : RandomInstanceProviderWithSRand {
    4551    public RandomInstanceClass4ProviderWithSRand() : base() { @class = 4; binWidth = binHeight = binDepth = 100; }
     52   
    4653  }
    4754  public class RandomInstanceClass5ProviderWithSRand : RandomInstanceProviderWithSRand {
    4855    public RandomInstanceClass5ProviderWithSRand() : base() { @class = 5; binWidth = binHeight = binDepth = 100; }
     56   
    4957  }
    5058
    … …  
    5563    }
    5664    protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
    57       w = rand.Next(1, 11);
    58       h = rand.Next(1, 11);
    59       d = rand.Next(1, 11);
     65      w = rand.Next(1, 10);
     66      h = rand.Next(1, 10);
     67      d = rand.Next(1, 10);
    6068    }
    6169  }
    … …  
    6674    }
    6775    protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
    68       w = rand.Next(1, 36);
    69       h = rand.Next(1, 36);
    70       d = rand.Next(1, 36);
     76      w = rand.Next(1, 35);
     77      h = rand.Next(1, 35);
     78      d = rand.Next(1, 35);
    7179    }
    7280  }
    … …  
    7785    }
    7886    protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
    79       w = rand.Next(1, 101);
    80       h = rand.Next(1, 101);
    81       d = rand.Next(1, 101);
     87      w = rand.Next(1, 100);
     88      h = rand.Next(1, 100);
     89      d = rand.Next(1, 100);
    8290    }
    8391  }
    … …  
    8795
    8896  public abstract class RandomInstanceProviderWithSRand : ProblemInstanceProvider<BPPData>, IProblemInstanceProvider<BPPData> {
     97
     98    /// <summary>
     99    /// Number of created test items. This items are used for packing them into the bin
     100    /// </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 };   
     102
     103    /// <summary>
     104    /// Number of instance for which should be created for each instance
     105    /// </summary>
     106    private static readonly int numberOfGeneratedInstances = 30;
     107
    89108    #region Random Generator srand48
    90109    protected class SRand48 : Item, IRandom {
    … …  
    173192    protected int binWidth, binHeight, binDepth;
    174193
     194    #region Common information for displaying it on the ui
     195   
    175196    public override string Name {
    176197      get { return string.Format("Martello, Pisinger, Vigo (class={0})", @class); }
    … …  
    189210    }
    190211
     212    #endregion
    191213    public RandomInstanceProviderWithSRand() : base() { }
    192214
     215   
     216    /// <summary>
     217    /// Returns a collection of data descriptors. Each descriptor contains the seed for the random generator.
     218    /// </summary>
     219    /// <returns></returns>
    193220    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
    194221      // 10 classes
    195       //var rand = new MersenneTwister(1234); // fixed seed to makes sure that instances are always the same
    196       foreach (int numItems in new int[] { 10, 15, 20, 25, 30, 35, 40, 45, 50, 60, 70, 80, 90, 100, 150, 200 }) {
    197         // get class parameters
    198         // generate 30 different instances for each class
    199         foreach (int instance in Enumerable.Range(1, 30)) {
    200           var rand = new SRand48((uint)(numItems + instance));
     222      foreach (int numItems in numberOfGeneratedTestItems) {
     223        for (int instance = 1; instance <= numberOfGeneratedInstances; instance++) {
    201224          string name = string.Format("n={0}-id={1:00} (class={2})", numItems, instance, @class);
    202           var dd = new RandomDataDescriptor(name, name, numItems, @class, seed: rand.Next());
    203           yield return dd;
    204         }
    205       }
    206     }
    207 
     225          /* As in the test programm of Silvano Martello, David Pisinger, Daniele Vigo given,
     226           * the seed of the instance provider will be calculated by adding the number of generated items and teh instance number.
     227           * This guarantees that the instances will always be the same
     228           */
     229          yield return new RandomDataDescriptor(name, name, numItems, @class, seed: numItems + instance);
     230        }
     231      }
     232    }
     233
     234   
    208235    public override BPPData LoadData(IDataDescriptor dd) {
    209236      var randDd = dd as RandomDataDescriptor;
    … …  
    224251    }
    225252
    226     // default implementation for class 1 .. 5
     253   
     254    /// <summary>
     255    /// Generates the dimensions for a item by using the given random generator
     256    /// </summary>
     257    /// <param name="rand">Given random generator</param>
     258    /// <param name="w">Calculated width of the item</param>
     259    /// <param name="h">Calculated height of the item</param>
     260    /// <param name="d">Calculated depth of the item</param>
    227261    protected virtual void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
    228       // for classes 1 - 5
    229262      Contract.Assert(@class >= 1 && @class <= 5);
    230       var weights = new double[] { 0.1, 0.1, 0.1, 0.1, 0.1 };
     263      /*var weights = new double[] { 0.1, 0.1, 0.1, 0.1, 0.1 };
    231264      weights[@class - 1] = 0.6;
    232265      var type = Enumerable.Range(1, 5).SampleProportional(rand, 1, weights).First();
    233 
    234       int minW, maxW;
    235       int minH, maxH;
    236       int minD, maxD;
    237       GetItemParameters(type, rand, binWidth, binHeight, binDepth,
    238         out minW, out maxW, out minH, out maxH, out minD, out maxD);
    239 
    240       w = rand.Next(minW, maxW + 1);
    241       h = rand.Next(minH, maxH + 1);
    242       d = rand.Next(minD, maxD + 1);
    243     }
    244 
    245     private void GetItemParameters(int type, IRandom rand,
    246       int w, int h, int d,
    247       out int minW, out int maxW, out int minH, out int maxH, out int minD, out int maxD) {
     266      */
     267
     268      // as by Martello and Vigo
     269      int type = @class;
     270      if (type <= 5) {
     271        var t = rand.Next(1, 10);
     272        if (t <= 5) {
     273          type = t;
     274        }
     275      }
     276
    248277      switch (type) {
    249         case 1: {
    250             minW = 1;
    251             maxW = w / 2; // integer division on purpose (see paper)
    252             minH = h * 2 / 3;
    253             maxH = h;
    254             minD = d * 2 / 3;
    255             maxD = d;
    256             break;
    257           }
    258         case 2: {
    259             minW = w * 2 / 3;
    260             maxW = w;
    261             minH = 1;
    262             maxH = h / 2;
    263             minD = d * 2 / 3;
    264             maxD = d;
    265             break;
    266           }
    267         case 3: {
    268             minW = w * 2 / 3;
    269             maxW = w;
    270             minH = h * 2 / 3;
    271             maxH = h;
    272             minD = 1;
    273             maxD = d / 2;
    274             break;
    275           }
    276         case 4: {
    277             minW = w / 2;
    278             maxW = w;
    279             minH = h / 2;
    280             maxH = h;
    281             minD = d / 2;
    282             maxD = d;
    283             break;
    284           }
    285         case 5: {
    286             minW = 1;
    287             maxW = w / 2;
    288             minH = 1;
    289             maxH = h / 2;
    290             minD = 1;
    291             maxD = d / 2;
    292             break;
    293           }
    294         default: {
     278        case 1:
     279          CreateInstanceDimensionsType1(rand, out w, out h, out d);
     280          break;
     281        case 2:
     282          CreateInstanceDimensionsType2(rand, out w, out h, out d);
     283          break;
     284        case 3:
     285          CreateInstanceDimensionsType3(rand, out w, out h, out d);
     286          break;
     287        case 4:
     288          CreateInstanceDimensionsType4(rand, out w, out h, out d);
     289          break;
     290        case 5:
     291          CreateInstanceDimensionsType5(rand, out w, out h, out d);
     292          break;
     293        default:
    295294            throw new InvalidProgramException();
    296           }
    297       }
    298     }
     295      }
     296    }
     297
     298   
     299    #region Instance dimensions generators for type 1 - 5
     300    private void CreateInstanceDimensionsType1(IRandom rand, out int w, out int h, out int d) {
     301      w = rand.Next(1, binWidth / 2);
     302      h = rand.Next((binHeight * 2) / 3, binHeight);
     303      d = rand.Next((binDepth * 2) / 3, binDepth);
     304    }
     305
     306    private void CreateInstanceDimensionsType2(IRandom rand, out int w, out int h, out int d) {
     307      w = rand.Next(((binWidth * 2) / 3), binWidth);
     308      h = rand.Next(1, binHeight / 2);
     309      d = rand.Next(((binDepth * 2) / 3), binDepth);
     310    }
     311
     312    private void CreateInstanceDimensionsType3(IRandom rand, out int w, out int h, out int d) {
     313      w = rand.Next(((binWidth * 2) / 3), binWidth);
     314      h = rand.Next(((binHeight * 2) / 3), binHeight);
     315      d = rand.Next(1, binDepth / 2);
     316    }
     317    private void CreateInstanceDimensionsType4(IRandom rand, out int w, out int h, out int d) {
     318      w = rand.Next(binWidth / 2, binWidth);
     319      h = rand.Next(binHeight / 2, binHeight);
     320      d = rand.Next(binDepth / 2, binDepth);
     321    }
     322    private void CreateInstanceDimensionsType5(IRandom rand, out int w, out int h, out int d) {
     323      w = rand.Next(1, binWidth / 2);
     324      h = rand.Next(1, binHeight / 2);
     325      d = rand.Next(1, binDepth / 2);
     326    }
     327   
     328    #endregion
     329
     330
    299331
    300332    public override bool CanImportData {
    … …  
    323355          else
    324356            writer.WriteLine("{0,-5} {1,-5} {2,-5}", instance.Items[i].Width, instance.Items[i].Height, instance.Items[i].Depth);
    325 
    326357        }
    327358        writer.Flush();
    328359      }
    329360    }
    330 
    331361  }
    332362}

  • 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.