Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
11/07/17 08:24:24 (7 years ago)
Author:
rhanghof
Message:

#2817

  • Extreme point bin packing does not need the occupation layer anymore
  • Changes at the fitting algorithm. Now they are packing the items as in the paper of S. Martello, D. Pisinger, D. Vigo described
Location:
branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances
Files:
1 deleted
1 edited

Legend:

Unmodified
Added
Removed
  • TabularUnified branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/RandomInstanceProvider.cs

    r15418 r15454  
    2626using System.IO;
    2727using System.Linq;
     28using System.Reflection;
    2829using HeuristicLab.Common;
    2930using HeuristicLab.Core;
    3031using HeuristicLab.Problems.Instances;
    3132using HeuristicLab.Random;
    32 
    33 namespace HeuristicLab.Problems.BinPacking3D {
     33using HeuristicLab.Problems.BinPacking.Random;
     34
     35namespace HeuristicLab.Problems.BinPacking3D.Instances {
    3436  // make sure that for each class we have a separate entry in the problem instance providers
     37
    3538  public class RandomInstanceClass1Provider : RandomInstanceProvider {
    36     public RandomInstanceClass1Provider() : base() { @class = 1; binWidth = binHeight = binDepth = 100; }
    37   }
     39    public RandomInstanceClass1Provider() : base(new SRand48()) { @class = 1; binWidth = binHeight = binDepth = 100; }
     40
     41  }
     42
    3843  public class RandomInstanceClass2Provider : RandomInstanceProvider {
    39     public RandomInstanceClass2Provider() : base() { @class = 2; binWidth = binHeight = binDepth = 100; }
     44    public RandomInstanceClass2Provider() : base(new SRand48()) { @class = 2; binWidth = binHeight = binDepth = 100; }
     45
    4046  }
    4147  public class RandomInstanceClass3Provider : RandomInstanceProvider {
    42     public RandomInstanceClass3Provider() : base() { @class = 3; binWidth = binHeight = binDepth = 100; }
     48    public RandomInstanceClass3Provider() : base(new SRand48()) { @class = 3; binWidth = binHeight = binDepth = 100; }
     49
    4350  }
    4451  public class RandomInstanceClass4Provider : RandomInstanceProvider {
    45     public RandomInstanceClass4Provider() : base() { @class = 4; binWidth = binHeight = binDepth = 100; }
     52    public RandomInstanceClass4Provider() : base(new SRand48()) { @class = 4; binWidth = binHeight = binDepth = 100; }
     53
    4654  }
    4755  public class RandomInstanceClass5Provider : RandomInstanceProvider {
    48     public RandomInstanceClass5Provider() : base() { @class = 5; binWidth = binHeight = binDepth = 100; }
     56    public RandomInstanceClass5Provider() : base(new SRand48()) { @class = 5; binWidth = binHeight = binDepth = 100; }
     57
    4958  }
    5059
    5160  public class RandomInstanceClass6Provider : RandomInstanceProvider {
    52     public RandomInstanceClass6Provider() : base() {
     61    public RandomInstanceClass6Provider() : base(new SRand48()) {
    5362      @class = 6;
    5463      binWidth = binHeight = binDepth = 10;
    5564    }
    5665    protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
    57       w = rand.Next(1, 11);
    58       h = rand.Next(1, 11);
    59       d = rand.Next(1, 11);
     66      w = rand.Next(1, 10);
     67      h = rand.Next(1, 10);
     68      d = rand.Next(1, 10);
    6069    }
    6170  }
    6271  public class RandomInstanceClass7Provider : RandomInstanceProvider {
    63     public RandomInstanceClass7Provider() : base() {
     72    public RandomInstanceClass7Provider() : base(new SRand48()) {
    6473      @class = 7;
    6574      binWidth = binHeight = binDepth = 40;
    6675    }
    6776    protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
    68       w = rand.Next(1, 36);
    69       h = rand.Next(1, 36);
    70       d = rand.Next(1, 36);
     77      w = rand.Next(1, 35);
     78      h = rand.Next(1, 35);
     79      d = rand.Next(1, 35);
    7180    }
    7281  }
    7382  public class RandomInstanceClass8Provider : RandomInstanceProvider {
    74     public RandomInstanceClass8Provider() : base() {
     83    public RandomInstanceClass8Provider() : base(new SRand48()) {
    7584      @class = 8;
    7685      binWidth = binHeight = binDepth = 100;
    7786    }
    7887    protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
    79       w = rand.Next(1, 101);
    80       h = rand.Next(1, 101);
    81       d = rand.Next(1, 101);
     88      w = rand.Next(1, 100);
     89      h = rand.Next(1, 100);
     90      d = rand.Next(1, 100);
    8291    }
    8392  }
     
    8897  public abstract class RandomInstanceProvider : ProblemInstanceProvider<BPPData>, IProblemInstanceProvider<BPPData> {
    8998
     99    /// <summary>
     100    /// Number of created test items. This items are used for packing them into the bin
     101    /// </summary>
     102    private readonly int[] _numberOfGeneratedTestItems = new int[] { 10, 15, 20, 25, 30, 35, 40, 45, 50, 60, 70, 80, 90, 100, 150, 200 };
     103
     104    /// <summary>
     105    /// Number of instance for which should be created for each instance
     106    /// </summary>
     107    private readonly int _numberOfGeneratedInstances;
     108
     109    /// <summary>
     110    /// Random generator for creating random packing items.
     111    /// </summary>
     112    private readonly IRandom _randomGenerator;
    90113
    91114
     
    93116    protected int binWidth, binHeight, binDepth;
    94117
     118    #region Common information for displaying on the ui
     119
    95120    public override string Name {
    96121      get { return string.Format("Martello, Pisinger, Vigo (class={0})", @class); }
     
    109134    }
    110135
    111     public RandomInstanceProvider() : base() { }
    112 
     136    #endregion
     137
     138
     139    public RandomInstanceProvider(IRandom randomGenerator, int numberOfGeneratedInstances = 10, int[] numberOfGeneratedTestItems = null) : base() {
     140      _numberOfGeneratedInstances = numberOfGeneratedInstances;
     141      if (numberOfGeneratedTestItems != null) {
     142        _numberOfGeneratedTestItems = numberOfGeneratedTestItems;
     143      }
     144      _randomGenerator = randomGenerator;
     145    }
     146
     147
     148    /// <summary>
     149    /// Returns a collection of data descriptors. Each descriptor contains the seed for the random generator.
     150    /// </summary>
     151    /// <returns></returns>
    113152    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
    114153      // 10 classes
    115       var rand = new MersenneTwister(1234); // fixed seed to makes sure that instances are always the same
    116       foreach (int numItems in new int[] { 10, 15, 20, 25, 30, 35, 40, 45, 50, 60, 70, 80, 90 }) {
    117         // get class parameters
    118         // generate 30 different instances for each class
    119         foreach (int instance in Enumerable.Range(1, 30)) {
     154      foreach (int numItems in _numberOfGeneratedTestItems) {
     155        for (int instance = 1; instance <= _numberOfGeneratedInstances; instance++) {
    120156          string name = string.Format("n={0}-id={1:00} (class={2})", numItems, instance, @class);
    121           var dd = new RandomDataDescriptor(name, name, numItems, @class, seed: rand.Next());
    122           yield return dd;
     157          /* As in the test programm of Silvano Martello, David Pisinger, Daniele Vigo given,
     158           * the seed of the instance provider will be calculated by adding the number of generated items and teh instance number.
     159           * This guarantees that the instances will always be the same
     160           */
     161          yield return new RandomDataDescriptor(name, name, numItems, @class, seed: numItems + instance);
    123162        }
    124163      }
    125164    }
     165
    126166
    127167    public override BPPData LoadData(IDataDescriptor dd) {
    128168      var randDd = dd as RandomDataDescriptor;
    129       if (randDd == null)
     169      if (randDd == null) {
    130170        throw new NotSupportedException("Cannot load data descriptor " + dd);
     171      }
    131172
    132173      var data = new BPPData() {
     
    134175        Items = new PackingItem[randDd.NumItems]
    135176      };
    136       var instanceRand = new MersenneTwister((uint)randDd.Seed);
     177      _randomGenerator.Reset(randDd.Seed);
    137178      for (int i = 0; i < randDd.NumItems; i++) {
    138179        int w, h, d;
    139         SampleItemParameters(instanceRand, out w, out h, out d);
     180        SampleItemParameters(_randomGenerator, out w, out h, out d);
    140181        data.Items[i] = new PackingItem(w, h, d, data.BinShape);
    141182      }
     
    143184    }
    144185
    145     // default implementation for class 1 .. 5
     186
     187    /// <summary>
     188    /// Generates the dimensions for a item by using the given random generator
     189    /// </summary>
     190    /// <param name="rand">Given random generator</param>
     191    /// <param name="w">Calculated width of the item</param>
     192    /// <param name="h">Calculated height of the item</param>
     193    /// <param name="d">Calculated depth of the item</param>
    146194    protected virtual void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
    147       // for classes 1 - 5
    148195      Contract.Assert(@class >= 1 && @class <= 5);
    149       var weights = new double[] { 0.1, 0.1, 0.1, 0.1, 0.1 };
     196      /*var weights = new double[] { 0.1, 0.1, 0.1, 0.1, 0.1 };
    150197      weights[@class - 1] = 0.6;
    151198      var type = Enumerable.Range(1, 5).SampleProportional(rand, 1, weights).First();
    152 
    153       int minW, maxW;
    154       int minH, maxH;
    155       int minD, maxD;
    156       GetItemParameters(type, rand, binWidth, binHeight, binDepth,
    157         out minW, out maxW, out minH, out maxH, out minD, out maxD);
    158 
    159       w = rand.Next(minW, maxW + 1);
    160       h = rand.Next(minH, maxH + 1);
    161       d = rand.Next(minD, maxD + 1);
    162     }
    163 
    164     private void GetItemParameters(int type, IRandom rand,
    165       int w, int h, int d,
    166       out int minW, out int maxW, out int minH, out int maxH, out int minD, out int maxD) {
     199      */
     200
     201      // as by Martello and Vigo
     202      int type = @class;
     203      if (type <= 5) {
     204        var t = rand.Next(1, 10);
     205        if (t <= 5) {
     206          type = t;
     207        }
     208      }
     209
    167210      switch (type) {
    168         case 1: {
    169             minW = 1;
    170             maxW = w / 2; // integer division on purpose (see paper)
    171             minH = h * 2 / 3;
    172             maxH = h;
    173             minD = d * 2 / 3;
    174             maxD = d;
    175             break;
    176           }
    177         case 2: {
    178             minW = w * 2 / 3;
    179             maxW = w;
    180             minH = 1;
    181             maxH = h / 2;
    182             minD = d * 2 / 3;
    183             maxD = d;
    184             break;
    185           }
    186         case 3: {
    187             minW = w * 2 / 3;
    188             maxW = w;
    189             minH = h * 2 / 3;
    190             maxH = h;
    191             minD = 1;
    192             maxD = d / 2;
    193             break;
    194           }
    195         case 4: {
    196             minW = w / 2;
    197             maxW = w;
    198             minH = h / 2;
    199             maxH = h;
    200             minD = d / 2;
    201             maxD = d;
    202             break;
    203           }
    204         case 5: {
    205             minW = 1;
    206             maxW = w / 2;
    207             minH = 1;
    208             maxH = h / 2;
    209             minD = 1;
    210             maxD = d / 2;
    211             break;
    212           }
    213         default: {
    214             throw new InvalidProgramException();
    215           }
    216       }
    217     }
     211        case 1:
     212          CreateInstanceDimensionsType1(rand, out w, out h, out d);
     213          break;
     214        case 2:
     215          CreateInstanceDimensionsType2(rand, out w, out h, out d);
     216          break;
     217        case 3:
     218          CreateInstanceDimensionsType3(rand, out w, out h, out d);
     219          break;
     220        case 4:
     221          CreateInstanceDimensionsType4(rand, out w, out h, out d);
     222          break;
     223        case 5:
     224          CreateInstanceDimensionsType5(rand, out w, out h, out d);
     225          break;
     226        default:
     227          throw new InvalidProgramException();
     228      }
     229    }
     230
     231
     232    #region Instance dimensions generators for type 1 - 5
     233    private void CreateInstanceDimensionsType1(IRandom rand, out int w, out int h, out int d) {
     234      w = rand.Next(1, binWidth / 2);
     235      h = rand.Next((binHeight * 2) / 3, binHeight);
     236      d = rand.Next((binDepth * 2) / 3, binDepth);
     237    }
     238
     239    private void CreateInstanceDimensionsType2(IRandom rand, out int w, out int h, out int d) {
     240      w = rand.Next(((binWidth * 2) / 3), binWidth);
     241      h = rand.Next(1, binHeight / 2);
     242      d = rand.Next(((binDepth * 2) / 3), binDepth);
     243    }
     244
     245    private void CreateInstanceDimensionsType3(IRandom rand, out int w, out int h, out int d) {
     246      w = rand.Next(((binWidth * 2) / 3), binWidth);
     247      h = rand.Next(((binHeight * 2) / 3), binHeight);
     248      d = rand.Next(1, binDepth / 2);
     249    }
     250    private void CreateInstanceDimensionsType4(IRandom rand, out int w, out int h, out int d) {
     251      w = rand.Next(binWidth / 2, binWidth);
     252      h = rand.Next(binHeight / 2, binHeight);
     253      d = rand.Next(binDepth / 2, binDepth);
     254    }
     255    private void CreateInstanceDimensionsType5(IRandom rand, out int w, out int h, out int d) {
     256      w = rand.Next(1, binWidth / 2);
     257      h = rand.Next(1, binHeight / 2);
     258      d = rand.Next(1, binDepth / 2);
     259    }
     260
     261    #endregion
     262
     263
    218264
    219265    public override bool CanImportData {
     
    242288          else
    243289            writer.WriteLine("{0,-5} {1,-5} {2,-5}", instance.Items[i].Width, instance.Items[i].Height, instance.Items[i].Depth);
    244 
    245290        }
    246291        writer.Flush();
    247292      }
    248293    }
    249 
    250294  }
    251295}
Note: See TracChangeset for help on using the changeset viewer.