Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
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/HeuristicLab.Problems.BinPacking.2D/3.3/Instances
Files:
2 deleted
2 moved

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/Instances/RandomDataDescriptor.cs

    r14062 r14063  
    2424
    2525namespace HeuristicLab.Problems.BinPacking2D {
    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    public int NumItems { get; set; }
     31    public int Seed { get; set; }
    3232
    33     internal BPPORLIBDataDescriptor(string name, string description, string instanceIdentifier, string solutionIdentifier) {
     33    internal RandomDataDescriptor(string name, string description, int numItems, int seed) {
    3434      this.Name = name;
    3535      this.Description = description;
    36       this.InstanceIdentifier = instanceIdentifier;
    37       this.SolutionIdentifier = solutionIdentifier;
     36      this.NumItems = numItems;
     37      this.Seed = seed;
    3838    }
    3939  }
  • branches/HeuristicLab.BinPacking/HeuristicLab.Problems.BinPacking.2D/3.3/Instances/RandomInstanceProvider.cs

    r14062 r14063  
    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.BinPacking2D {
    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() {
     36      @class = 1;
     37      binWidth = binHeight = 10;
     38    }
     39    protected override void SampleItemParameters(IRandom rand, out int w, out int h) {
     40      w = rand.Next(1, 11);
     41      h = rand.Next(1, 11);
     42    }
     43  }
     44  public class RandomInstanceClass2Provider : RandomInstanceProvider {
     45    public RandomInstanceClass2Provider() : base() {
     46      @class = 2;
     47      binWidth = binHeight = 30;
     48    }
     49    protected override void SampleItemParameters(IRandom rand, out int w, out int h) {
     50      w = rand.Next(1, 11);
     51      h = rand.Next(1, 11);
     52    }
     53  }
     54  public class RandomInstanceClass3Provider : RandomInstanceProvider {
     55    public RandomInstanceClass3Provider() : base() {
     56      @class = 3;
     57      binWidth = binHeight = 40;
     58    }
     59    protected override void SampleItemParameters(IRandom rand, out int w, out int h) {
     60      w = rand.Next(1, 36);
     61      h = rand.Next(1, 36);
     62    }
     63  }
     64
     65  public class RandomInstanceClass4Provider : RandomInstanceProvider {
     66    public RandomInstanceClass4Provider() : base() {
     67      @class = 4;
     68      binWidth = binHeight = 100;
     69    }
     70    protected override void SampleItemParameters(IRandom rand, out int w, out int h) {
     71      w = rand.Next(1, 36);
     72      h = rand.Next(1, 36);
     73    }
     74  }
     75  public class RandomInstanceClass5Provider : RandomInstanceProvider {
     76    public RandomInstanceClass5Provider() : base() {
     77      @class = 5;
     78      binWidth = binHeight = 100;
     79    }
     80    protected override void SampleItemParameters(IRandom rand, out int w, out int h) {
     81      w = rand.Next(1, 101);
     82      h = rand.Next(1, 101);
     83    }
     84  }
     85  public class RandomInstanceClass6Provider : RandomInstanceProvider {
     86    public RandomInstanceClass6Provider() : base() {
     87      @class = 6;
     88      binWidth = binHeight = 300;
     89    }
     90    protected override void SampleItemParameters(IRandom rand, out int w, out int h) {
     91      w = rand.Next(1, 101);
     92      h = rand.Next(1, 101);
     93    }
     94  }
     95  public class RandomInstanceClass7Provider : RandomInstanceProvider {
     96    public RandomInstanceClass7Provider() : base() { @class = 7; binWidth = binHeight = 100; }
     97  }
     98  public class RandomInstanceClass8Provider : RandomInstanceProvider {
     99    public RandomInstanceClass8Provider() : base() { @class = 8; binWidth = binHeight = 100; }
     100  }
     101  public class RandomInstanceClass9Provider : RandomInstanceProvider {
     102    public RandomInstanceClass9Provider() : base() { @class = 9; binWidth = binHeight = 100; }
     103  }
     104  public class RandomInstanceClass10Provider : RandomInstanceProvider {
     105    public RandomInstanceClass10Provider() : base() { @class = 10; binWidth = binHeight = 100; }
     106  }
     107  public abstract class RandomInstanceProvider : ProblemInstanceProvider<BPPData>, IProblemInstanceProvider<BPPData> {
     108
     109    protected int @class;
     110    protected int binWidth, binHeight;
    34111
    35112    public override string Name {
    36       get { return "ORLIB BPP"; }
     113      get { return string.Format("Lodi, Martelli, Vigo (class={0})", @class); }
    37114    }
    38115
    39116    public override string Description {
    40       get { return "Bin packing problems from the Operations Research Library."; }
     117      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."; }
    41118    }
    42119
    43120    public override Uri WebLink {
    44       get { return new Uri("http://people.brunel.ac.uk/~mastjjb/jeb/orlib/binpacktwoinfo.html"); }
     121      get { return null; }
    45122    }
    46123
    47124    public override string ReferencePublication {
    48       get { return String.Empty; }
    49     }
     125      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."; }
     126    }
     127
     128    public RandomInstanceProvider() : base() { }
    50129
    51130    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);
     131      // 10 classes
     132      var rand = new MersenneTwister(1234); // fixed seed to makes sure that instances are always the same
     133      foreach (int numItems in new int[] { 20, 40, 60, 80, 100 }) {
     134        // get class parameters
     135        // generate 30 different instances for each class
     136        foreach (int instance in Enumerable.Range(1, 30)) {
     137          string name = string.Format("n={0}-id={1:00} (class={2})", numItems, instance, @class);
     138          var dd = new RandomDataDescriptor(name, name, numItems, seed: rand.Next());
     139          yield return dd;
    65140        }
    66141      }
    67142    }
    68143
    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         }
     144    public override BPPData LoadData(IDataDescriptor dd) {
     145      var randDd = dd as RandomDataDescriptor;
     146      if (randDd == null) throw new NotSupportedException("Cannot load data descriptor " + dd);
     147
     148      var data = new BPPData() {
     149        BinShape = new PackingShape(binWidth, binHeight),
     150        Items = new PackingItem[randDd.NumItems]
     151      };
     152      var instanceRand = new MersenneTwister((uint)randDd.Seed);
     153      for (int i = 0; i < randDd.NumItems; i++) {
     154        int w, h;
     155        SampleItemParameters(instanceRand, out w, out h);
     156        data.Items[i] = new PackingItem(w, h, data.BinShape);
     157      }
     158      return data;
     159    }
     160
     161    // default implementation for class 7 .. 10
     162    protected virtual void SampleItemParameters(IRandom rand, out int w, out int h) {
     163      // for classes 1 - 5
     164      Contract.Assert(@class >= 7 && @class <= 10);
     165      var weights = new double[] { 0.1, 0.1, 0.1, 0.1 };
     166      weights[@class - 7] = 0.7;
     167      var type = Enumerable.Range(1, 4).SampleProportional(rand, 1, weights).First();
     168
     169      int minW, maxW;
     170      int minH, maxH;
     171      GetItemParameters(type, rand, binWidth, binHeight,
     172        out minW, out maxW, out minH, out maxH);
     173
     174      w = rand.Next(minW, maxW + 1);
     175      h = rand.Next(minH, maxH + 1);
     176    }
     177
     178    private void GetItemParameters(int type, IRandom rand,
     179      int w, int h,
     180      out int minW, out int maxW, out int minH, out int maxH) {
     181      switch (type) {
     182        case 1: {
     183            minW = w * 2 / 3; maxW = w; // integer division on purpose (see paper)
     184            minH = 1; maxH = h / 2;
     185            break;
     186          }
     187        case 2: {
     188            minW = 1; maxW = w / 2;
     189            minH = h * 2 / 3; maxH = h;
     190            break;
     191          }
     192        case 3: {
     193            minW = w / 2; maxW = w;
     194            minH = h / 2; maxH = h;
     195            break;
     196          }
     197        case 4: {
     198            minW = 1; maxW = w / 2;
     199            minH = 1; maxH = h / 2;
     200            break;
     201          }
     202        default: {
     203            throw new InvalidProgramException();
     204          }
    82205      }
    83206    }
    84207
    85208    public override bool CanImportData {
    86       get { return true; }
     209      get { return false; }
    87210    }
    88211    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;
     212      throw new NotSupportedException();
    93213    }
    94214
     
    97217    }
    98218
    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     }
     219    public override void ExportData(BPPData instance, string file) {
     220      using (Stream stream = new FileStream(file, FileMode.OpenOrCreate, FileAccess.Write)) {
     221        Export(instance, stream);
     222      }
     223    }
     224    public static void Export(BPPData instance, Stream stream) {
     225
     226      using (var writer = new StreamWriter(stream)) {
     227        writer.WriteLine(String.Format("{0,-5} {1,-5}   WBIN,HBIN", instance.BinShape.Width, instance.BinShape.Height));
     228        for (int i = 0; i < instance.NumItems; i++) {
     229          if (i == 0)
     230            writer.WriteLine("{0,-5} {1,-5}   W(I),H(I),I=1,...,N", instance.Items[i].Width, instance.Items[i].Height);
     231          else
     232            writer.WriteLine("{0,-5} {1,-5}", instance.Items[i].Width, instance.Items[i].Height);
     233
     234        }
     235        writer.Flush();
     236      }
     237    }
     238
    111239  }
    112240}
Note: See TracChangeset for help on using the changeset viewer.