Changeset 14062


Ignore:
Timestamp:
07/13/16 20:39:47 (10 months 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:
2 deleted
1 edited
2 moved

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3/HeuristicLab.Problems.BinPacking3D-3.3.csproj

    r14055 r14062  
    151151      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Problems.Instances-3.3.dll</HintPath>
    152152    </Reference>
     153    <Reference Include="HeuristicLab.Random-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     154      <SpecificVersion>False</SpecificVersion>
     155      <HintPath>..\..\..\..\trunk\sources\bin\HeuristicLab.Random-3.3.dll</HintPath>
     156    </Reference>
    153157    <Reference Include="System" />
    154158    <Reference Include="System.Core" />
     
    170174    <Compile Include="I3DOperator.cs" />
    171175    <Compile Include="Instances\BPPData.cs" />
    172     <Compile Include="Instances\BPPInstanceProvider.cs" />
    173     <Compile Include="Instances\BPPORLIBDataDescriptor.cs" />
    174     <Compile Include="Instances\BPPORLIBParser.cs" />
     176    <Compile Include="Instances\RandomDataDescriptor.cs" />
     177    <Compile Include="Instances\RandomInstanceProvider.cs" />
    175178    <Compile Include="MoveEvaluators\PackingMoveEvaluator3DGV.cs" />
    176179    <Compile Include="MoveEvaluators\PackingMoveEvaluator3DMCV.cs" />
     
    187190  <ItemGroup>
    188191    <None Include="HeuristicLab.snk" />
    189     <EmbeddedResource Include="Instances\Data\BPPORLIB.zip" />
    190192    <None Include="Properties\AssemblyInfo.cs.frame" />
    191193    <None Include="Plugin.cs.frame" />
  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3/Instances/RandomDataDescriptor.cs

    r14061 r14062  
    2424
    2525namespace HeuristicLab.Problems.BinPacking3D {
    26   internal class BPPORLIBDataDescriptor : IDataDescriptor {
    27     public string Name { get; internal set; }
    28     public string Description { get; internal set; }
     26  internal class RandomDataDescriptor : IDataDescriptor {
     27    public string Name { get; private set; }
     28    public string Description { get; private set; }
    2929
    30     internal string InstanceIdentifier { get; set; }
    31     internal string SolutionIdentifier { get; set; }
     30    internal int NumItems { get; private set; }
     31    internal int Class { get; private set; }
    3232
    33     internal BPPORLIBDataDescriptor(string name, string description, string instanceIdentifier, string solutionIdentifier) {
     33    internal int Seed { get; private set; }
     34
     35    internal RandomDataDescriptor(string name, string description, int numItems, int @class, int seed) {
    3436      this.Name = name;
    3537      this.Description = description;
    36       this.InstanceIdentifier = instanceIdentifier;
    37       this.SolutionIdentifier = solutionIdentifier;
     38      this.NumItems = numItems;
     39      this.Class = @class;
     40      this.Seed = seed;
    3841    }
    3942  }
  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.3D/3.3/Instances/RandomInstanceProvider.cs

    r14061 r14062  
    11#region License Information
    22/* HeuristicLab
    3  * Copyright (C) 2002-2015 Joseph Helm and Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     3 * Copyright (C) 2002 - 2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
    44 *
    55 * This file is part of HeuristicLab.
     
    2323using System;
    2424using System.Collections.Generic;
     25using System.Diagnostics.Contracts;
    2526using System.IO;
    26 using System.IO.Compression;
    2727using System.Linq;
    28 using System.Reflection;
    29 using System.Text.RegularExpressions;
     28using HeuristicLab.Core;
    3029using HeuristicLab.Problems.Instances;
     30using HeuristicLab.Random;
    3131
    3232namespace HeuristicLab.Problems.BinPacking3D {
    33   public class BPPORLIBInstanceProvider : ProblemInstanceProvider<BPPData>, IProblemInstanceProvider<BPPData> {
     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  }
     49
     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;
     88    protected int binWidth, binHeight, binDepth;
    3489
    3590    public override string Name {
    36       get { return "ORLIB BPP"; }
     91      get { return string.Format("Martello, Pisinger, Vigo (class={0})", @class); }
    3792    }
    3893
    3994    public override string Description {
    40       get { return "Bin packing problems from the Operations Research Library."; }
     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."; }
    4196    }
    4297
    4398    public override Uri WebLink {
    44       get { return new Uri("http://www.diku.dk/~pisinger/new3dbpp/readme.3dbpp"); }
     99      get { return null; }
    45100    }
    46101
    47102    public override string ReferencePublication {
    48       get { return String.Empty; }
    49     }
     103      get { return "Martello, Pisinger, Vigo: 'The Three-Dimensional Bin Packing Problem', Operations Research Vol 48, Issue 2, 2000, pp. 256-267."; }
     104    }
     105
     106    public RandomInstanceProvider() : base() { }
    50107
    51108    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
    52       var instanceArchiveName = GetResourceName("BPPORLIB.zip");
    53       if (String.IsNullOrEmpty(instanceArchiveName)) yield break;
    54 
    55 
    56       using (var file = new ZipArchive(GetType().Assembly.GetManifestResourceStream(instanceArchiveName))) {
    57 
    58         foreach (var entry in file.Entries.OrderBy(x => x.Name)) {
    59           if (string.IsNullOrWhiteSpace(entry.Name)) continue;
    60           yield return new BPPORLIBDataDescriptor(
    61             name: Path.GetFileNameWithoutExtension(entry.Name),
    62             description: GetDescription(),
    63             instanceIdentifier: entry.FullName,
    64             solutionIdentifier: null);
     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;
    65118        }
    66119      }
    67120    }
    68121
    69     public override BPPData LoadData(IDataDescriptor id) {
    70       var descriptor = (BPPORLIBDataDescriptor)id;
    71       var instanceArchiveName = GetResourceName("BPPORLIB.zip");
    72       using (var instancesZipFile = new ZipArchive(GetType().Assembly.GetManifestResourceStream(instanceArchiveName))) {
    73         var entry = instancesZipFile.GetEntry(descriptor.InstanceIdentifier);
    74 
    75         using (var stream = entry.Open()) {
    76           var instance = BPPORLIBParser.Parse(stream);
    77           instance.Name = id.Name;
    78           instance.Description = id.Description;
    79 
    80           return instance;
    81         }
     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;
     137    }
     138
     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);
     156    }
     157
     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          }
    82195      }
    83196    }
    84197
    85198    public override bool CanImportData {
    86       get { return true; }
     199      get { return false; }
    87200    }
    88201    public override BPPData ImportData(string path) {
    89       var instance = BPPORLIBParser.Parse(path);
    90       instance.Name = Path.GetFileName(path);
    91       instance.Description = "Loaded from file \"" + path + "\" on " + DateTime.Now;
    92       return instance;
     202      throw new NotSupportedException();
    93203    }
    94204
     
    97207    }
    98208
    99     public override void ExportData(BPPData instance, string path) {
    100       BPPORLIBParser.Export(instance, path);
    101     }
    102 
    103     private string GetDescription() {
    104       return "Embedded instance of plugin version " + Assembly.GetExecutingAssembly().GetCustomAttributes(typeof(AssemblyFileVersionAttribute), true).Cast<AssemblyFileVersionAttribute>().First().Version + ".";
    105     }
    106 
    107     protected virtual string GetResourceName(string fileName) {
    108       return Assembly.GetExecutingAssembly().GetManifestResourceNames()
    109         .SingleOrDefault(x => Regex.Match(x, @".*\.Data\." + fileName).Success);
    110     }
     209    public override void ExportData(BPPData instance, string file) {
     210      using (Stream stream = new FileStream(file, FileMode.OpenOrCreate, FileAccess.Write)) {
     211        Export(instance, stream);
     212      }
     213    }
     214    public static void Export(BPPData instance, Stream stream) {
     215
     216      using (var writer = new StreamWriter(stream)) {
     217        writer.WriteLine(String.Format("{0,-5} {1,-5} {2,-5}   WBIN,HBIN,DBIN", instance.BinShape.Width, instance.BinShape.Height, instance.BinShape.Depth));
     218        for (int i = 0; i < instance.NumItems; i++) {
     219          if (i == 0)
     220            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);
     221          else
     222            writer.WriteLine("{0,-5} {1,-5} {2,-5}", instance.Items[i].Width, instance.Items[i].Height, instance.Items[i].Depth);
     223
     224        }
     225        writer.Flush();
     226      }
     227    }
     228
    111229  }
    112230}
Note: See TracChangeset for help on using the changeset viewer.