Changeset 14062

Timestamp:

07/13/16 20:39:47 (8 years ago)

Author:

gkronber

Message:

#1966: reimplemented problem instance generation from paper Silvano Martello, David Pisinger Daniele Vigo, "The Three-Dimensional Bin Packing Problem"

Location:

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3

Files:

• HeuristicLab.Problems.BinPacking3D-3.3.csproj (modified) (3 diffs)
• Instances/BPPORLIBParser.cs (deleted)
• Instances/Data (deleted)
• Instances/RandomDataDescriptor.cs (moved) (moved from branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3/Instances/BPPORLIBDataDescriptor.cs) (1 diff)
• Instances/RandomInstanceProvider.cs (moved) (moved from branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3/Instances/BPPInstanceProvider.cs) (3 diffs)

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3/HeuristicLab.Problems.BinPacking3D-3.3.csproj

@@ -151 +151 @@
       <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Problems.Instances-3.3.dll</HintPath>
     </Reference>
+    <Reference Include="HeuristicLab.Random-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <SpecificVersion>False</SpecificVersion>
+      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Random-3.3.dll</HintPath>
+    </Reference>
     <Reference Include="System" />
     <Reference Include="System.Core" />
@@ -170 +174 @@
     <Compile Include="I3DOperator.cs" />
     <Compile Include="Instances\BPPData.cs" />
-    <Compile Include="Instances\BPPInstanceProvider.cs" />
-    <Compile Include="Instances\BPPORLIBDataDescriptor.cs" />
-    <Compile Include="Instances\BPPORLIBParser.cs" />
+    <Compile Include="Instances\RandomDataDescriptor.cs" />
+    <Compile Include="Instances\RandomInstanceProvider.cs" />
     <Compile Include="MoveEvaluators\PackingMoveEvaluator3DGV.cs" />
     <Compile Include="MoveEvaluators\PackingMoveEvaluator3DMCV.cs" />
@@ -187 +190 @@
   <ItemGroup>
     <None Include="HeuristicLab.snk" />
-    <EmbeddedResource Include="Instances\Data\BPPORLIB.zip" />
     <None Include="Properties\AssemblyInfo.cs.frame" />
     <None Include="Plugin.cs.frame" />

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3/Instances/RandomDataDescriptor.cs

@@ -24 +24 @@
 
 namespace HeuristicLab.Problems.BinPacking3D {
-  internal class BPPORLIBDataDescriptor : IDataDescriptor {
-    public string Name { get; internal set; }
-    public string Description { get; internal set; }
+  internal class RandomDataDescriptor : IDataDescriptor {
+    public string Name { get; private set; }
+    public string Description { get; private set; }
 
-    internal string InstanceIdentifier { get; set; }
-    internal string SolutionIdentifier { get; set; }
+    internal int NumItems { get; private set; }
+    internal int Class { get; private set; }
 
-    internal BPPORLIBDataDescriptor(string name, string description, string instanceIdentifier, string solutionIdentifier) {
+    internal int Seed { get; private set; }
+
+    internal RandomDataDescriptor(string name, string description, int numItems, int @class, int seed) {
       this.Name = name;
       this.Description = description;
-      this.InstanceIdentifier = instanceIdentifier;
-      this.SolutionIdentifier = solutionIdentifier;
+      this.NumItems = numItems;
+      this.Class = @class;
+      this.Seed = seed;
     }
   }

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3/Instances/RandomInstanceProvider.cs

@@ -1 +1 @@
 #region License Information
 /* HeuristicLab
- * Copyright (C) 2002-2015 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL)
+ * Copyright (C) 2002 - 2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
  *
  * This file is part of HeuristicLab.
@@ -23 +23 @@
 using System;
 using System.Collections.Generic;
+using System.Diagnostics.Contracts;
 using System.IO;
-using System.IO.Compression;
 using System.Linq;
-using System.Reflection;
-using System.Text.RegularExpressions;
+using HeuristicLab.Core;
 using HeuristicLab.Problems.Instances;
+using HeuristicLab.Random;
 
 namespace HeuristicLab.Problems.BinPacking3D {
-  public class BPPORLIBInstanceProvider : ProblemInstanceProvider<BPPData>, IProblemInstanceProvider<BPPData> {
+  // 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 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 "ORLIB BPP"; }
+      get { return string.Format("Martello, Pisinger, Vigo (class={0})", @class); }
     }
 
     public override string Description {
-      get { return "Bin packing problems from the Operations Research Library."; }
+      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."; }
     }
 
     public override Uri WebLink {
-      get { return new Uri("http://www.diku.dk/~pisinger/new3dbpp/readme.3dbpp"); }
+      get { return null; }
     }
 
     public override string ReferencePublication {
-      get { return String.Empty; }
-    }
+      get { return "Martello, Pisinger, Vigo: 'The Three-Dimensional Bin Packing Problem', Operations Research Vol 48, Issue 2, 2000, pp. 256-267."; }
+    }
+
+    public RandomInstanceProvider() : base() { }
 
     public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
-      var instanceArchiveName = GetResourceName("BPPORLIB.zip");
-      if (String.IsNullOrEmpty(instanceArchiveName)) yield break;
-
-
-      using (var file = new ZipArchive(GetType().Assembly.GetManifestResourceStream(instanceArchiveName))) {
-
-        foreach (var entry in file.Entries.OrderBy(x => x.Name)) {
-          if (string.IsNullOrWhiteSpace(entry.Name)) continue;
-          yield return new BPPORLIBDataDescriptor(
-            name: Path.GetFileNameWithoutExtension(entry.Name),
-            description: GetDescription(),
-            instanceIdentifier: entry.FullName,
-            solutionIdentifier: null);
+      // 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;
         }
       }
     }
 
-    public override BPPData LoadData(IDataDescriptor id) {
-      var descriptor = (BPPORLIBDataDescriptor)id;
-      var instanceArchiveName = GetResourceName("BPPORLIB.zip");
-      using (var instancesZipFile = new ZipArchive(GetType().Assembly.GetManifestResourceStream(instanceArchiveName))) {
-        var entry = instancesZipFile.GetEntry(descriptor.InstanceIdentifier);
-
-        using (var stream = entry.Open()) {
-          var instance = BPPORLIBParser.Parse(stream);
-          instance.Name = id.Name;
-          instance.Description = id.Description;
-
-          return instance;
-        }
+    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;
+    }
+
+    // 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 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 bool CanImportData {
-      get { return true; }
+      get { return false; }
     }
     public override BPPData ImportData(string path) {
-      var instance = BPPORLIBParser.Parse(path);
-      instance.Name = Path.GetFileName(path);
-      instance.Description = "Loaded from file \"" + path + "\" on " + DateTime.Now;
-      return instance;
+      throw new NotSupportedException();
     }
 
@@ -97 +207 @@
     }
 
-    public override void ExportData(BPPData instance, string path) {
-      BPPORLIBParser.Export(instance, path);
-    }
-
-    private string GetDescription() {
-      return "Embedded instance of plugin version " + Assembly.GetExecutingAssembly().GetCustomAttributes(typeof(AssemblyFileVersionAttribute), true).Cast<AssemblyFileVersionAttribute>().First().Version + ".";
-    }
-
-    protected virtual string GetResourceName(string fileName) {
-      return Assembly.GetExecutingAssembly().GetManifestResourceNames()
-        .SingleOrDefault(x => Regex.Match(x, @".*\.Data\." + fileName).Success);
-    }
+    public override void ExportData(BPPData instance, string file) {
+      using (Stream stream = new FileStream(file, FileMode.OpenOrCreate, FileAccess.Write)) {
+        Export(instance, stream);
+      }
+    }
+    public static void Export(BPPData instance, Stream stream) {
+
+      using (var writer = new StreamWriter(stream)) {
+        writer.WriteLine(String.Format("{0,-5} {1,-5} {2,-5}   WBIN,HBIN,DBIN", instance.BinShape.Width, instance.BinShape.Height, instance.BinShape.Depth));
+        for (int i = 0; i < instance.NumItems; i++) {
+          if (i == 0)
+            writer.WriteLine("{0,-5} {1,-5} {2,-5}   W(I),H(I)D(I),I=1,...,N", instance.Items[i].Width, instance.Items[i].Height, instance.Items[i].Depth);
+          else
+            writer.WriteLine("{0,-5} {1,-5} {2,-5}", instance.Items[i].Width, instance.Items[i].Height, instance.Items[i].Depth);
+
+        }
+        writer.Flush();
+      }
+    }
+
   }
 }