Changeset 14838 for branches/BinPackingExtension

Timestamp:

04/10/17 16:04:04 (8 years ago)

Author:

abeham

Message:

Added some benchmark instances

Location:

branches/BinPackingExtension

Files:

• BinPacking.sln (modified) (1 diff)
• HeuristicLab.Problems.BinPacking/3.3/3D/Instances/3D-Instances.zip (added)
• HeuristicLab.Problems.BinPacking/3.3/3D/Instances/RealisticInstanceProvider.cs (copied) (copied from branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/RandomInstanceProvider.cs) (2 diffs)
• HeuristicLab.Problems.BinPacking/3.3/3D/Instances/ThreeDInstanceDescriptor.cs (added)
• HeuristicLab.Problems.BinPacking/3.3/3D/Instances/ThreeDInstanceParser.cs (added)
• HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj (modified) (2 diffs)
• PreBuildEvent.cmd (added)

branches/BinPackingExtension/BinPacking.sln

@@ -4 +4 @@
 VisualStudioVersion = 14.0.25420.1
 MinimumVisualStudioVersion = 10.0.40219.1
+Project("{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}"
+EndProject
+Project("{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}"
+EndProject
 Global
+  GlobalSection(SolutionConfigurationPlatforms) = preSolution
+    Debug|Any CPU = Debug|Any CPU
+    Debug|x64 = Debug|x64
+    Debug|x86 = Debug|x86
+    Release|Any CPU = Release|Any CPU
+    Release|x64 = Release|x64
+    Release|x86 = Release|x86
+  EndGlobalSection
+  GlobalSection(ProjectConfigurationPlatforms) = postSolution
+    {F8A55094-3CD5-4034-B0CA-5BD7FFB016D4}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
+    {F8A55094-3CD5-4034-B0CA-5BD7FFB016D4}.Debug|Any CPU.Build.0 = Debug|Any CPU
+    {F8A55094-3CD5-4034-B0CA-5BD7FFB016D4}.Debug|x64.ActiveCfg = Debug|x64
+    {F8A55094-3CD5-4034-B0CA-5BD7FFB016D4}.Debug|x64.Build.0 = Debug|x64
+    {F8A55094-3CD5-4034-B0CA-5BD7FFB016D4}.Debug|x86.ActiveCfg = Debug|x86
+    {F8A55094-3CD5-4034-B0CA-5BD7FFB016D4}.Debug|x86.Build.0 = Debug|x86
+    {F8A55094-3CD5-4034-B0CA-5BD7FFB016D4}.Release|Any CPU.ActiveCfg = Release|Any CPU
+    {F8A55094-3CD5-4034-B0CA-5BD7FFB016D4}.Release|Any CPU.Build.0 = Release|Any CPU
+    {F8A55094-3CD5-4034-B0CA-5BD7FFB016D4}.Release|x64.ActiveCfg = Release|x64
+    {F8A55094-3CD5-4034-B0CA-5BD7FFB016D4}.Release|x64.Build.0 = Release|x64
+    {F8A55094-3CD5-4034-B0CA-5BD7FFB016D4}.Release|x86.ActiveCfg = Release|x86
+    {F8A55094-3CD5-4034-B0CA-5BD7FFB016D4}.Release|x86.Build.0 = Release|x86
+    {8CFC7A61-E214-44DC-96B3-4CEA9B8E958E}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
+    {8CFC7A61-E214-44DC-96B3-4CEA9B8E958E}.Debug|Any CPU.Build.0 = Debug|Any CPU
+    {8CFC7A61-E214-44DC-96B3-4CEA9B8E958E}.Debug|x64.ActiveCfg = Debug|x64
+    {8CFC7A61-E214-44DC-96B3-4CEA9B8E958E}.Debug|x64.Build.0 = Debug|x64
+    {8CFC7A61-E214-44DC-96B3-4CEA9B8E958E}.Debug|x86.ActiveCfg = Debug|x86
+    {8CFC7A61-E214-44DC-96B3-4CEA9B8E958E}.Debug|x86.Build.0 = Debug|x86
+    {8CFC7A61-E214-44DC-96B3-4CEA9B8E958E}.Release|Any CPU.ActiveCfg = Release|Any CPU
+    {8CFC7A61-E214-44DC-96B3-4CEA9B8E958E}.Release|Any CPU.Build.0 = Release|Any CPU
+    {8CFC7A61-E214-44DC-96B3-4CEA9B8E958E}.Release|x64.ActiveCfg = Release|x64
+    {8CFC7A61-E214-44DC-96B3-4CEA9B8E958E}.Release|x64.Build.0 = Release|x64
+    {8CFC7A61-E214-44DC-96B3-4CEA9B8E958E}.Release|x86.ActiveCfg = Release|x86
+    {8CFC7A61-E214-44DC-96B3-4CEA9B8E958E}.Release|x86.Build.0 = Release|x86
+  EndGlobalSection
   GlobalSection(SolutionProperties) = preSolution
     HideSolutionNode = FALSE

branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/RealisticInstanceProvider.cs

@@ -20 +20 @@
 #endregion
 
-
 using System;
 using System.Collections.Generic;
-using System.Diagnostics.Contracts;
 using System.IO;
+using System.IO.Compression;
 using System.Linq;
-using HeuristicLab.Core;
+using System.Reflection;
+using System.Text.RegularExpressions;
 using HeuristicLab.Problems.Instances;
-using HeuristicLab.Random;
 
 namespace HeuristicLab.Problems.BinPacking3D {
-  // make sure that for each class we have a separate entry in the problem instance providers
-  public class RandomInstanceClass1Provider : RandomInstanceProvider {
-    public RandomInstanceClass1Provider() : base() { @class = 1; binWidth = binHeight = binDepth = 100; }
-  }
-  public class RandomInstanceClass2Provider : RandomInstanceProvider {
-    public RandomInstanceClass2Provider() : base() { @class = 2; binWidth = binHeight = binDepth = 100; }
-  }
-  public class RandomInstanceClass3Provider : RandomInstanceProvider {
-    public RandomInstanceClass3Provider() : base() { @class = 3; binWidth = binHeight = binDepth = 100; }
-  }
-  public class RandomInstanceClass4Provider : RandomInstanceProvider {
-    public RandomInstanceClass4Provider() : base() { @class = 4; binWidth = binHeight = binDepth = 100; }
-  }
-  public class RandomInstanceClass5Provider : RandomInstanceProvider {
-    public RandomInstanceClass5Provider() : base() { @class = 5; binWidth = binHeight = binDepth = 100; }
-  }
+  public class RealisticInstanceProvider : ProblemInstanceProvider<BPPData> {
+    protected virtual string FileName { get { return "3D-Instances"; } }
 
-  public class RandomInstanceClass6Provider : RandomInstanceProvider {
-    public RandomInstanceClass6Provider() : base() {
-      @class = 6;
-      binWidth = binHeight = binDepth = 10;
-    }
-    protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
-      w = rand.Next(1, 11);
-      h = rand.Next(1, 11);
-      d = rand.Next(1, 11);
-    }
-  }
-  public class RandomInstanceClass7Provider : RandomInstanceProvider {
-    public RandomInstanceClass7Provider() : base() {
-      @class = 7;
-      binWidth = binHeight = binDepth = 40;
-    }
-    protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
-      w = rand.Next(1, 36);
-      h = rand.Next(1, 36);
-      d = rand.Next(1, 36);
-    }
-  }
-  public class RandomInstanceClass8Provider : RandomInstanceProvider {
-    public RandomInstanceClass8Provider() : base() {
-      @class = 8;
-      binWidth = binHeight = binDepth = 100;
-    }
-    protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
-      w = rand.Next(1, 101);
-      h = rand.Next(1, 101);
-      d = rand.Next(1, 101);
-    }
-  }
-
-  // class 9 from the paper (all-fill) is not implemented 
-  public abstract class RandomInstanceProvider : ProblemInstanceProvider<BPPData>, IProblemInstanceProvider<BPPData> {
-
-    protected int @class;
     protected int binWidth, binHeight, binDepth;
 
     public override string Name {
-      get { return string.Format("Martello, Pisinger, Vigo (class={0})", @class); }
+      get { return "Realistic"; }
     }
 
     public override string Description {
-      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."; }
+      get { return "Problem instances derived from real-world data."; }
     }
 
@@ -101 +48 @@
 
     public override string ReferencePublication {
-      get { return "Martello, Pisinger, Vigo: 'The Three-Dimensional Bin Packing Problem', Operations Research Vol 48, Issue 2, 2000, pp. 256-267."; }
+      get { return null; }
     }
 
-    public RandomInstanceProvider() : base() { }
+    public RealisticInstanceProvider() : base() { }
 
     public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
-      // 10 classes
-      var rand = new MersenneTwister(1234); // fixed seed to makes sure that instances are always the same
-      foreach (int numItems in new int[] { 10, 15, 20, 25, 30, 35, 40, 45, 50, 60, 70, 80, 90 }) {
-        // get class parameters
-        // generate 30 different instances for each class
-        foreach (int instance in Enumerable.Range(1, 30)) {
-          string name = string.Format("n={0}-id={1:00} (class={2})", numItems, instance, @class);
-          var dd = new RandomDataDescriptor(name, name, numItems, @class, seed: rand.Next());
-          yield return dd;
+      var instanceArchiveName = GetResourceName(FileName + @"\.zip");
+      if (String.IsNullOrEmpty(instanceArchiveName)) yield break;
+
+      using (var instanceStream = new ZipArchive(GetType().Assembly.GetManifestResourceStream(instanceArchiveName), ZipArchiveMode.Read)) {
+        foreach (var entry in instanceStream.Entries.Select(x => x.Name).OrderBy(x => x)) {
+          yield return new ThreeDInstanceDescriptor(Path.GetFileNameWithoutExtension(entry), GetDescription(), entry);
         }
       }
     }
 
-    public override BPPData LoadData(IDataDescriptor dd) {
-      var randDd = dd as RandomDataDescriptor;
-      if (randDd == null) throw new NotSupportedException("Cannot load data descriptor " + dd);
-
-      var data = new BPPData() {
-        BinShape = new PackingShape(binWidth, binHeight, binDepth),
-        Items = new PackingItem[randDd.NumItems]
-      };
-      var instanceRand = new MersenneTwister((uint)randDd.Seed);
-      for (int i = 0; i < randDd.NumItems; i++) {
-        int w, h, d;
-        SampleItemParameters(instanceRand, out w, out h, out d);
-        data.Items[i] = new PackingItem(w, h, d, data.BinShape);
-      }
-      return data;
+    private string GetResourceName(string fileName) {
+      return Assembly.GetExecutingAssembly().GetManifestResourceNames()
+              .Where(x => Regex.Match(x, @".*\.Instances\." + fileName).Success).SingleOrDefault();
     }
 
-    // default implementation for class 1 .. 5
-    protected virtual void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
-      // for classes 1 - 5
-      Contract.Assert(@class >= 1 && @class <= 5);
-      var weights = new double[] { 0.1, 0.1, 0.1, 0.1, 0.1 };
-      weights[@class - 1] = 0.6;
-      var type = Enumerable.Range(1, 5).SampleProportional(rand, 1, weights).First();
-
-      int minW, maxW;
-      int minH, maxH;
-      int minD, maxD;
-      GetItemParameters(type, rand, binWidth, binHeight, binDepth,
-        out minW, out maxW, out minH, out maxH, out minD, out maxD);
-
-      w = rand.Next(minW, maxW + 1);
-      h = rand.Next(minH, maxH + 1);
-      d = rand.Next(minD, maxD + 1);
+    private string GetDescription() {
+      return "Embedded instance of plugin version " + Assembly.GetExecutingAssembly().GetCustomAttributes(typeof(AssemblyFileVersionAttribute), true).Cast<AssemblyFileVersionAttribute>().First().Version + ".";
     }
 
-    private void GetItemParameters(int type, IRandom rand,
-      int w, int h, int d,
-      out int minW, out int maxW, out int minH, out int maxH, out int minD, out int maxD) {
-      switch (type) {
-        case 1: {
-            minW = 1; maxW = w / 2; // integer division on purpose (see paper)
-            minH = h * 2 / 3; maxH = h;
-            minD = d * 2 / 3; maxD = d;
-            break;
-          }
-        case 2: {
-            minW = w * 2 / 3; maxW = w;
-            minH = 1; maxH = h / 2;
-            minD = d * 2 / 3; maxD = d;
-            break;
-          }
-        case 3: {
-            minW = w * 2 / 3; maxW = w;
-            minH = h * 2 / 3; maxH = h;
-            minD = 1; maxD = d / 2;
-            break;
-          }
-        case 4: {
-            minW = w / 2; maxW = w;
-            minH = h / 2; maxH = h;
-            minD = d / 2; maxD = d;
-            break;
-          }
-        case 5: {
-            minW = 1; maxW = w / 2;
-            minH = 1; maxH = h / 2;
-            minD = 1; maxD = d / 2;
-            break;
-          }
-        default: {
-            throw new InvalidProgramException();
-          }
+    public override BPPData LoadData(IDataDescriptor dd) {
+      var desc = dd as ThreeDInstanceDescriptor;
+      if (desc == null) throw new NotSupportedException("Cannot load data descriptor " + dd);
+      var instanceArchiveName = GetResourceName(FileName + @"\.zip");
+      using (
+        var instancesZipFile = new ZipArchive(GetType().Assembly.GetManifestResourceStream(instanceArchiveName),
+          ZipArchiveMode.Read)) {
+        var entry = instancesZipFile.GetEntry(desc.InstanceIdentifier);
+
+        using (var stream = entry.Open()) {
+          var parser = new ThreeDInstanceParser();
+          parser.Parse(stream);
+
+          return new BPPData() {
+            Name = desc.Name,
+            Description = desc.Description,
+            BinShape = parser.Bin,
+            Items = parser.Items.ToArray()
+          };
+        }
       }
     }
 
     public override bool CanImportData {
-      get { return false; }
+      get { return true; }
     }
+
     public override BPPData ImportData(string path) {
-      throw new NotSupportedException();
+      using (var stream = new FileStream(path, FileMode.Open, FileAccess.Read, FileShare.ReadWrite)) {
+        var parser = new ThreeDInstanceParser();
+        parser.Parse(stream);
+
+        return new BPPData() {
+          Name = Path.GetFileNameWithoutExtension(path),
+          Description = "Imported instance from " + path,
+          BinShape = parser.Bin,
+          Items = parser.Items.ToArray()
+        };
+      }
     }
 

branches/BinPackingExtension/HeuristicLab.Problems.BinPacking/3.3/HeuristicLab.Problems.BinPacking-3.3.csproj

@@ -158 +158 @@
     <Compile Include="3D\Evaluators\BinUtilizationEvaluator.cs" />
     <Compile Include="3D\Evaluators\PackingRatioEvaluator.cs" />
+    <Compile Include="3D\Instances\ThreeDInstanceDescriptor.cs" />
     <Compile Include="3D\Instances\BPPData.cs" />
     <Compile Include="3D\Instances\RandomDataDescriptor.cs" />
+    <Compile Include="3D\Instances\RealisticInstanceProvider.cs" />
     <Compile Include="3D\Instances\RandomInstanceProvider.cs" />
+    <Compile Include="3D\Instances\ThreeDInstanceParser.cs" />
     <Compile Include="3D\IntegerVectorEncoding\BottomLeftIntegerVectorDecoder.cs" />
     <Compile Include="3D\IntegerVectorEncoding\ExtremePointIntegerVectorDecoder.cs" />
@@ -196 +199 @@
   </ItemGroup>
   <ItemGroup>
+    <EmbeddedResource Include="3D\Instances\3D-Instances.zip" />
     <None Include="HeuristicLab.snk" />
     <None Include="Properties\AssemblyInfo.cs.frame" />