Changeset 14063

Timestamp:

07/13/16 21:02:15 (8 years ago)

Author:

gkronber

Message:

#1966: implemented random instance generation for 2d BPP instances

Location:

branches/HeuristicLab.BinPacking

Files:

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

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/HeuristicLab.Problems.BinPacking2D-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" />
@@ -166 +170 @@
     <Compile Include="Decoders\EP\ExtremePointPackingSequenceDecoder2D.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="Interfaces\I2DGVDecoder.cs" />
     <Compile Include="Interfaces\I2DMCVDecoder.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.2D/3.3/Instances/RandomDataDescriptor.cs

@@ -24 +24 @@
 
 namespace HeuristicLab.Problems.BinPacking2D {
-  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; }
+    public int NumItems { get; set; }
+    public int Seed { get; set; }
 
-    internal BPPORLIBDataDescriptor(string name, string description, string instanceIdentifier, string solutionIdentifier) {
+    internal RandomDataDescriptor(string name, string description, int numItems, int seed) {
       this.Name = name;
       this.Description = description;
-      this.InstanceIdentifier = instanceIdentifier;
-      this.SolutionIdentifier = solutionIdentifier;
+      this.NumItems = numItems;
+      this.Seed = seed;
     }
   }

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/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.BinPacking2D {
-  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 = 10;
+    }
+    protected override void SampleItemParameters(IRandom rand, out int w, out int h) {
+      w = rand.Next(1, 11);
+      h = rand.Next(1, 11);
+    }
+  }
+  public class RandomInstanceClass2Provider : RandomInstanceProvider {
+    public RandomInstanceClass2Provider() : base() {
+      @class = 2;
+      binWidth = binHeight = 30;
+    }
+    protected override void SampleItemParameters(IRandom rand, out int w, out int h) {
+      w = rand.Next(1, 11);
+      h = rand.Next(1, 11);
+    }
+  }
+  public class RandomInstanceClass3Provider : RandomInstanceProvider {
+    public RandomInstanceClass3Provider() : base() {
+      @class = 3;
+      binWidth = binHeight = 40;
+    }
+    protected override void SampleItemParameters(IRandom rand, out int w, out int h) {
+      w = rand.Next(1, 36);
+      h = rand.Next(1, 36);
+    }
+  }
+
+  public class RandomInstanceClass4Provider : RandomInstanceProvider {
+    public RandomInstanceClass4Provider() : base() {
+      @class = 4;
+      binWidth = binHeight = 100;
+    }
+    protected override void SampleItemParameters(IRandom rand, out int w, out int h) {
+      w = rand.Next(1, 36);
+      h = rand.Next(1, 36);
+    }
+  }
+  public class RandomInstanceClass5Provider : RandomInstanceProvider {
+    public RandomInstanceClass5Provider() : base() {
+      @class = 5;
+      binWidth = binHeight = 100;
+    }
+    protected override void SampleItemParameters(IRandom rand, out int w, out int h) {
+      w = rand.Next(1, 101);
+      h = rand.Next(1, 101);
+    }
+  }
+  public class RandomInstanceClass6Provider : RandomInstanceProvider {
+    public RandomInstanceClass6Provider() : base() {
+      @class = 6;
+      binWidth = binHeight = 300;
+    }
+    protected override void SampleItemParameters(IRandom rand, out int w, out int h) {
+      w = rand.Next(1, 101);
+      h = rand.Next(1, 101);
+    }
+  }
+  public class RandomInstanceClass7Provider : RandomInstanceProvider {
+    public RandomInstanceClass7Provider() : base() { @class = 7; binWidth = binHeight = 100; }
+  }
+  public class RandomInstanceClass8Provider : RandomInstanceProvider {
+    public RandomInstanceClass8Provider() : base() { @class = 8; binWidth = binHeight = 100; }
+  }
+  public class RandomInstanceClass9Provider : RandomInstanceProvider {
+    public RandomInstanceClass9Provider() : base() { @class = 9; binWidth = binHeight = 100; }
+  }
+  public class RandomInstanceClass10Provider : RandomInstanceProvider {
+    public RandomInstanceClass10Provider() : base() { @class = 10; binWidth = binHeight = 100; }
+  }
+  public abstract class RandomInstanceProvider : ProblemInstanceProvider<BPPData>, IProblemInstanceProvider<BPPData> {
+
+    protected int @class;
+    protected int binWidth, binHeight;
 
     public override string Name {
-      get { return "ORLIB BPP"; }
+      get { return string.Format("Lodi, Martelli, Vigo (class={0})", @class); }
     }
 
     public override string Description {
-      get { return "Bin packing problems from the Operations Research Library."; }
+      get { return "Randomly generated 2d bin packing problems as described in Lodi, Martello, and Vigo. 'Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems.' INFORMS Journal on Computing 11.4 (1999): 345-357."; }
     }
 
     public override Uri WebLink {
-      get { return new Uri("http://people.brunel.ac.uk/~mastjjb/jeb/orlib/binpacktwoinfo.html"); }
+      get { return null; }
     }
 
     public override string ReferencePublication {
-      get { return String.Empty; }
-    }
+      get { return "Lodi, Martello, and Vigo. 'Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems.' INFORMS Journal on Computing 11.4 (1999): 345-357."; }
+    }
+
+    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[] { 20, 40, 60, 80, 100 }) {
+        // 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, 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),
+        Items = new PackingItem[randDd.NumItems]
+      };
+      var instanceRand = new MersenneTwister((uint)randDd.Seed);
+      for (int i = 0; i < randDd.NumItems; i++) {
+        int w, h;
+        SampleItemParameters(instanceRand, out w, out h);
+        data.Items[i] = new PackingItem(w, h, data.BinShape);
+      }
+      return data;
+    }
+
+    // default implementation for class 7 .. 10
+    protected virtual void SampleItemParameters(IRandom rand, out int w, out int h) {
+      // for classes 1 - 5
+      Contract.Assert(@class >= 7 && @class <= 10);
+      var weights = new double[] { 0.1, 0.1, 0.1, 0.1 };
+      weights[@class - 7] = 0.7;
+      var type = Enumerable.Range(1, 4).SampleProportional(rand, 1, weights).First();
+
+      int minW, maxW;
+      int minH, maxH;
+      GetItemParameters(type, rand, binWidth, binHeight,
+        out minW, out maxW, out minH, out maxH);
+
+      w = rand.Next(minW, maxW + 1);
+      h = rand.Next(minH, maxH + 1);
+    }
+
+    private void GetItemParameters(int type, IRandom rand,
+      int w, int h,
+      out int minW, out int maxW, out int minH, out int maxH) {
+      switch (type) {
+        case 1: {
+            minW = w * 2 / 3; maxW = w; // integer division on purpose (see paper)
+            minH = 1; maxH = h / 2;
+            break;
+          }
+        case 2: {
+            minW = 1; maxW = w / 2;
+            minH = h * 2 / 3; maxH = h;
+            break;
+          }
+        case 3: {
+            minW = w / 2; maxW = w;
+            minH = h / 2; maxH = h;
+            break;
+          }
+        case 4: {
+            minW = 1; maxW = w / 2;
+            minH = 1; maxH = h / 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 +217 @@
     }
 
-    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}   WBIN,HBIN", instance.BinShape.Width, instance.BinShape.Height));
+        for (int i = 0; i < instance.NumItems; i++) {
+          if (i == 0)
+            writer.WriteLine("{0,-5} {1,-5}   W(I),H(I),I=1,...,N", instance.Items[i].Width, instance.Items[i].Height);
+          else
+            writer.WriteLine("{0,-5} {1,-5}", instance.Items[i].Width, instance.Items[i].Height);
+
+        }
+        writer.Flush();
+      }
+    }
+
   }
 }

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/Plugin.cs.frame

@@ -39 +39 @@
   [PluginDependency("HeuristicLab.Persistence", "3.3")]
   [PluginDependency("HeuristicLab.Problems.Instances", "3.3")]
+  [PluginDependency("HeuristicLab.Random", "3.3")]
   public class Plugin : PluginBase {
   }

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

@@ -29 +29 @@
 
     internal int NumItems { get; private set; }
-    internal int Class { get; private set; }
-
     internal int Seed { get; private set; }
 
@@ -37 +35 @@
       this.Description = description;
       this.NumItems = numItems;
-      this.Class = @class;
       this.Seed = seed;
     }

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

@@ -218 +218 @@
         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);
+            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);

branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3/Plugin.cs.frame

@@ -39 +39 @@
   [PluginDependency("HeuristicLab.Persistence", "3.3")]
   [PluginDependency("HeuristicLab.Problems.Instances", "3.3")]
+  [PluginDependency("HeuristicLab.Random", "3.3")]
   public class Plugin : PluginBase {
   }