Changeset 14838


Ignore:
Timestamp:
04/10/17 16:04:04 (4 months ago)
Author:
abeham
Message:

Added some benchmark instances

Location:
branches/BinPackingExtension
Files:
4 added
2 edited
1 copied

Legend:

Unmodified
Added
Removed
  • branches/BinPackingExtension/BinPacking.sln

    r14835 r14838  
    44VisualStudioVersion = 14.0.25420.1
    55MinimumVisualStudioVersion = 10.0.40219.1
     6Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.BinPacking-3.3", "HeuristicLab.Problems.BinPacking\3.3\HeuristicLab.Problems.BinPacking-3.3.csproj", "{F8A55094-3CD5-4034-B0CA-5BD7FFB016D4}"
     7EndProject
     8Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.BinPacking.Views-3.3", "HeuristicLab.Problems.BinPacking.Views\3.3\HeuristicLab.Problems.BinPacking.Views-3.3.csproj", "{8CFC7A61-E214-44DC-96B3-4CEA9B8E958E}"
     9EndProject
    610Global
     11  GlobalSection(SolutionConfigurationPlatforms) = preSolution
     12    Debug|Any CPU = Debug|Any CPU
     13    Debug|x64 = Debug|x64
     14    Debug|x86 = Debug|x86
     15    Release|Any CPU = Release|Any CPU
     16    Release|x64 = Release|x64
     17    Release|x86 = Release|x86
     18  EndGlobalSection
     19  GlobalSection(ProjectConfigurationPlatforms) = postSolution
     20    {F8A55094-3CD5-4034-B0CA-5BD7FFB016D4}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
     21    {F8A55094-3CD5-4034-B0CA-5BD7FFB016D4}.Debug|Any CPU.Build.0 = Debug|Any CPU
     22    {F8A55094-3CD5-4034-B0CA-5BD7FFB016D4}.Debug|x64.ActiveCfg = Debug|x64
     23    {F8A55094-3CD5-4034-B0CA-5BD7FFB016D4}.Debug|x64.Build.0 = Debug|x64
     24    {F8A55094-3CD5-4034-B0CA-5BD7FFB016D4}.Debug|x86.ActiveCfg = Debug|x86
     25    {F8A55094-3CD5-4034-B0CA-5BD7FFB016D4}.Debug|x86.Build.0 = Debug|x86
     26    {F8A55094-3CD5-4034-B0CA-5BD7FFB016D4}.Release|Any CPU.ActiveCfg = Release|Any CPU
     27    {F8A55094-3CD5-4034-B0CA-5BD7FFB016D4}.Release|Any CPU.Build.0 = Release|Any CPU
     28    {F8A55094-3CD5-4034-B0CA-5BD7FFB016D4}.Release|x64.ActiveCfg = Release|x64
     29    {F8A55094-3CD5-4034-B0CA-5BD7FFB016D4}.Release|x64.Build.0 = Release|x64
     30    {F8A55094-3CD5-4034-B0CA-5BD7FFB016D4}.Release|x86.ActiveCfg = Release|x86
     31    {F8A55094-3CD5-4034-B0CA-5BD7FFB016D4}.Release|x86.Build.0 = Release|x86
     32    {8CFC7A61-E214-44DC-96B3-4CEA9B8E958E}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
     33    {8CFC7A61-E214-44DC-96B3-4CEA9B8E958E}.Debug|Any CPU.Build.0 = Debug|Any CPU
     34    {8CFC7A61-E214-44DC-96B3-4CEA9B8E958E}.Debug|x64.ActiveCfg = Debug|x64
     35    {8CFC7A61-E214-44DC-96B3-4CEA9B8E958E}.Debug|x64.Build.0 = Debug|x64
     36    {8CFC7A61-E214-44DC-96B3-4CEA9B8E958E}.Debug|x86.ActiveCfg = Debug|x86
     37    {8CFC7A61-E214-44DC-96B3-4CEA9B8E958E}.Debug|x86.Build.0 = Debug|x86
     38    {8CFC7A61-E214-44DC-96B3-4CEA9B8E958E}.Release|Any CPU.ActiveCfg = Release|Any CPU
     39    {8CFC7A61-E214-44DC-96B3-4CEA9B8E958E}.Release|Any CPU.Build.0 = Release|Any CPU
     40    {8CFC7A61-E214-44DC-96B3-4CEA9B8E958E}.Release|x64.ActiveCfg = Release|x64
     41    {8CFC7A61-E214-44DC-96B3-4CEA9B8E958E}.Release|x64.Build.0 = Release|x64
     42    {8CFC7A61-E214-44DC-96B3-4CEA9B8E958E}.Release|x86.ActiveCfg = Release|x86
     43    {8CFC7A61-E214-44DC-96B3-4CEA9B8E958E}.Release|x86.Build.0 = Release|x86
     44  EndGlobalSection
    745  GlobalSection(SolutionProperties) = preSolution
    846    HideSolutionNode = FALSE
  • branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/RealisticInstanceProvider.cs

    r14835 r14838  
    2020#endregion
    2121
    22 
    2322using System;
    2423using System.Collections.Generic;
    25 using System.Diagnostics.Contracts;
    2624using System.IO;
     25using System.IO.Compression;
    2726using System.Linq;
    28 using HeuristicLab.Core;
     27using System.Reflection;
     28using System.Text.RegularExpressions;
    2929using HeuristicLab.Problems.Instances;
    30 using HeuristicLab.Random;
    3130
    3231namespace HeuristicLab.Problems.BinPacking3D {
    33   // make sure that for each class we have a separate entry in the problem instance providers
    34   public class RandomInstanceClass1Provider : RandomInstanceProvider {
    35     public RandomInstanceClass1Provider() : base() { @class = 1; binWidth = binHeight = binDepth = 100; }
    36   }
    37   public class RandomInstanceClass2Provider : RandomInstanceProvider {
    38     public RandomInstanceClass2Provider() : base() { @class = 2; binWidth = binHeight = binDepth = 100; }
    39   }
    40   public class RandomInstanceClass3Provider : RandomInstanceProvider {
    41     public RandomInstanceClass3Provider() : base() { @class = 3; binWidth = binHeight = binDepth = 100; }
    42   }
    43   public class RandomInstanceClass4Provider : RandomInstanceProvider {
    44     public RandomInstanceClass4Provider() : base() { @class = 4; binWidth = binHeight = binDepth = 100; }
    45   }
    46   public class RandomInstanceClass5Provider : RandomInstanceProvider {
    47     public RandomInstanceClass5Provider() : base() { @class = 5; binWidth = binHeight = binDepth = 100; }
    48   }
     32  public class RealisticInstanceProvider : ProblemInstanceProvider<BPPData> {
     33    protected virtual string FileName { get { return "3D-Instances"; } }
    4934
    50   public class RandomInstanceClass6Provider : RandomInstanceProvider {
    51     public RandomInstanceClass6Provider() : base() {
    52       @class = 6;
    53       binWidth = binHeight = binDepth = 10;
    54     }
    55     protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
    56       w = rand.Next(1, 11);
    57       h = rand.Next(1, 11);
    58       d = rand.Next(1, 11);
    59     }
    60   }
    61   public class RandomInstanceClass7Provider : RandomInstanceProvider {
    62     public RandomInstanceClass7Provider() : base() {
    63       @class = 7;
    64       binWidth = binHeight = binDepth = 40;
    65     }
    66     protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
    67       w = rand.Next(1, 36);
    68       h = rand.Next(1, 36);
    69       d = rand.Next(1, 36);
    70     }
    71   }
    72   public class RandomInstanceClass8Provider : RandomInstanceProvider {
    73     public RandomInstanceClass8Provider() : base() {
    74       @class = 8;
    75       binWidth = binHeight = binDepth = 100;
    76     }
    77     protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
    78       w = rand.Next(1, 101);
    79       h = rand.Next(1, 101);
    80       d = rand.Next(1, 101);
    81     }
    82   }
    83 
    84   // class 9 from the paper (all-fill) is not implemented
    85   public abstract class RandomInstanceProvider : ProblemInstanceProvider<BPPData>, IProblemInstanceProvider<BPPData> {
    86 
    87     protected int @class;
    8835    protected int binWidth, binHeight, binDepth;
    8936
    9037    public override string Name {
    91       get { return string.Format("Martello, Pisinger, Vigo (class={0})", @class); }
     38      get { return "Realistic"; }
    9239    }
    9340
    9441    public override string Description {
    95       get { return "Randomly generated 3d bin packing problems as described in Martello, Pisinger, Vigo: 'The Three-Dimensional Bin Packing Problem', Operations Research Vol 48, Issue 2, 2000, pp. 256-267."; }
     42      get { return "Problem instances derived from real-world data."; }
    9643    }
    9744
     
    10148
    10249    public override string ReferencePublication {
    103       get { return "Martello, Pisinger, Vigo: 'The Three-Dimensional Bin Packing Problem', Operations Research Vol 48, Issue 2, 2000, pp. 256-267."; }
     50      get { return null; }
    10451    }
    10552
    106     public RandomInstanceProvider() : base() { }
     53    public RealisticInstanceProvider() : base() { }
    10754
    10855    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
    109       // 10 classes
    110       var rand = new MersenneTwister(1234); // fixed seed to makes sure that instances are always the same
    111       foreach (int numItems in new int[] { 10, 15, 20, 25, 30, 35, 40, 45, 50, 60, 70, 80, 90 }) {
    112         // get class parameters
    113         // generate 30 different instances for each class
    114         foreach (int instance in Enumerable.Range(1, 30)) {
    115           string name = string.Format("n={0}-id={1:00} (class={2})", numItems, instance, @class);
    116           var dd = new RandomDataDescriptor(name, name, numItems, @class, seed: rand.Next());
    117           yield return dd;
     56      var instanceArchiveName = GetResourceName(FileName + @"\.zip");
     57      if (String.IsNullOrEmpty(instanceArchiveName)) yield break;
     58
     59      using (var instanceStream = new ZipArchive(GetType().Assembly.GetManifestResourceStream(instanceArchiveName), ZipArchiveMode.Read)) {
     60        foreach (var entry in instanceStream.Entries.Select(x => x.Name).OrderBy(x => x)) {
     61          yield return new ThreeDInstanceDescriptor(Path.GetFileNameWithoutExtension(entry), GetDescription(), entry);
    11862        }
    11963      }
    12064    }
    12165
    122     public override BPPData LoadData(IDataDescriptor dd) {
    123       var randDd = dd as RandomDataDescriptor;
    124       if (randDd == null) throw new NotSupportedException("Cannot load data descriptor " + dd);
    125 
    126       var data = new BPPData() {
    127         BinShape = new PackingShape(binWidth, binHeight, binDepth),
    128         Items = new PackingItem[randDd.NumItems]
    129       };
    130       var instanceRand = new MersenneTwister((uint)randDd.Seed);
    131       for (int i = 0; i < randDd.NumItems; i++) {
    132         int w, h, d;
    133         SampleItemParameters(instanceRand, out w, out h, out d);
    134         data.Items[i] = new PackingItem(w, h, d, data.BinShape);
    135       }
    136       return data;
     66    private string GetResourceName(string fileName) {
     67      return Assembly.GetExecutingAssembly().GetManifestResourceNames()
     68              .Where(x => Regex.Match(x, @".*\.Instances\." + fileName).Success).SingleOrDefault();
    13769    }
    13870
    139     // default implementation for class 1 .. 5
    140     protected virtual void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
    141       // for classes 1 - 5
    142       Contract.Assert(@class >= 1 && @class <= 5);
    143       var weights = new double[] { 0.1, 0.1, 0.1, 0.1, 0.1 };
    144       weights[@class - 1] = 0.6;
    145       var type = Enumerable.Range(1, 5).SampleProportional(rand, 1, weights).First();
    146 
    147       int minW, maxW;
    148       int minH, maxH;
    149       int minD, maxD;
    150       GetItemParameters(type, rand, binWidth, binHeight, binDepth,
    151         out minW, out maxW, out minH, out maxH, out minD, out maxD);
    152 
    153       w = rand.Next(minW, maxW + 1);
    154       h = rand.Next(minH, maxH + 1);
    155       d = rand.Next(minD, maxD + 1);
     71    private string GetDescription() {
     72      return "Embedded instance of plugin version " + Assembly.GetExecutingAssembly().GetCustomAttributes(typeof(AssemblyFileVersionAttribute), true).Cast<AssemblyFileVersionAttribute>().First().Version + ".";
    15673    }
    15774
    158     private void GetItemParameters(int type, IRandom rand,
    159       int w, int h, int d,
    160       out int minW, out int maxW, out int minH, out int maxH, out int minD, out int maxD) {
    161       switch (type) {
    162         case 1: {
    163             minW = 1; maxW = w / 2; // integer division on purpose (see paper)
    164             minH = h * 2 / 3; maxH = h;
    165             minD = d * 2 / 3; maxD = d;
    166             break;
    167           }
    168         case 2: {
    169             minW = w * 2 / 3; maxW = w;
    170             minH = 1; maxH = h / 2;
    171             minD = d * 2 / 3; maxD = d;
    172             break;
    173           }
    174         case 3: {
    175             minW = w * 2 / 3; maxW = w;
    176             minH = h * 2 / 3; maxH = h;
    177             minD = 1; maxD = d / 2;
    178             break;
    179           }
    180         case 4: {
    181             minW = w / 2; maxW = w;
    182             minH = h / 2; maxH = h;
    183             minD = d / 2; maxD = d;
    184             break;
    185           }
    186         case 5: {
    187             minW = 1; maxW = w / 2;
    188             minH = 1; maxH = h / 2;
    189             minD = 1; maxD = d / 2;
    190             break;
    191           }
    192         default: {
    193             throw new InvalidProgramException();
    194           }
     75    public override BPPData LoadData(IDataDescriptor dd) {
     76      var desc = dd as ThreeDInstanceDescriptor;
     77      if (desc == null) throw new NotSupportedException("Cannot load data descriptor " + dd);
     78      var instanceArchiveName = GetResourceName(FileName + @"\.zip");
     79      using (
     80        var instancesZipFile = new ZipArchive(GetType().Assembly.GetManifestResourceStream(instanceArchiveName),
     81          ZipArchiveMode.Read)) {
     82        var entry = instancesZipFile.GetEntry(desc.InstanceIdentifier);
     83
     84        using (var stream = entry.Open()) {
     85          var parser = new ThreeDInstanceParser();
     86          parser.Parse(stream);
     87
     88          return new BPPData() {
     89            Name = desc.Name,
     90            Description = desc.Description,
     91            BinShape = parser.Bin,
     92            Items = parser.Items.ToArray()
     93          };
     94        }
    19595      }
    19696    }
    19797
    19898    public override bool CanImportData {
    199       get { return false; }
     99      get { return true; }
    200100    }
     101
    201102    public override BPPData ImportData(string path) {
    202       throw new NotSupportedException();
     103      using (var stream = new FileStream(path, FileMode.Open, FileAccess.Read, FileShare.ReadWrite)) {
     104        var parser = new ThreeDInstanceParser();
     105        parser.Parse(stream);
     106
     107        return new BPPData() {
     108          Name = Path.GetFileNameWithoutExtension(path),
     109          Description = "Imported instance from " + path,
     110          BinShape = parser.Bin,
     111          Items = parser.Items.ToArray()
     112        };
     113      }
    203114    }
    204115
  • branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj

    r14835 r14838  
    158158    <Compile Include="3D\Evaluators\BinUtilizationEvaluator.cs" />
    159159    <Compile Include="3D\Evaluators\PackingRatioEvaluator.cs" />
     160    <Compile Include="3D\Instances\ThreeDInstanceDescriptor.cs" />
    160161    <Compile Include="3D\Instances\BPPData.cs" />
    161162    <Compile Include="3D\Instances\RandomDataDescriptor.cs" />
     163    <Compile Include="3D\Instances\RealisticInstanceProvider.cs" />
    162164    <Compile Include="3D\Instances\RandomInstanceProvider.cs" />
     165    <Compile Include="3D\Instances\ThreeDInstanceParser.cs" />
    163166    <Compile Include="3D\IntegerVectorEncoding\BottomLeftIntegerVectorDecoder.cs" />
    164167    <Compile Include="3D\IntegerVectorEncoding\ExtremePointIntegerVectorDecoder.cs" />
     
    196199  </ItemGroup>
    197200  <ItemGroup>
     201    <EmbeddedResource Include="3D\Instances\3D-Instances.zip" />
    198202    <None Include="HeuristicLab.snk" />
    199203    <None Include="Properties\AssemblyInfo.cs.frame" />
Note: See TracChangeset for help on using the changeset viewer.