Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2817-BinPackingSpeedup/HeuristicLab.Problems.BinPacking/3.3/3D/Instances/RandomInstanceProviderWithSRand.cs @ 15423

Last change on this file since 15423 was 15423, checked in by rhanghof, 5 years ago

#2817: - Now the new RandomInstanceProvider creates the same instances as in the specification given by Martello, Pisinger and Vigo.

  • Now the unit tests are testing the new RandomInstanceProvider.
File size: 12.6 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2016 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22
23using System;
24using System.Collections.Generic;
25using System.Diagnostics.Contracts;
26using System.IO;
27using System.Linq;
28using System.Reflection;
29using HeuristicLab.Common;
30using HeuristicLab.Core;
31using HeuristicLab.Problems.Instances;
32using HeuristicLab.Random;
33
34namespace HeuristicLab.Problems.BinPacking3D {
35  // make sure that for each class we have a separate entry in the problem instance providers
36 
37  public class RandomInstanceClass1ProviderWithSRand : RandomInstanceProviderWithSRand {
38    public RandomInstanceClass1ProviderWithSRand() : base() { @class = 1; binWidth = binHeight = binDepth = 100; }
39   
40  }
41
42  public class RandomInstanceClass2ProviderWithSRand : RandomInstanceProviderWithSRand {
43    public RandomInstanceClass2ProviderWithSRand() : base() { @class = 2; binWidth = binHeight = binDepth = 100; }
44   
45  }
46  public class RandomInstanceClass3ProviderWithSRand : RandomInstanceProviderWithSRand {
47    public RandomInstanceClass3ProviderWithSRand() : base() { @class = 3; binWidth = binHeight = binDepth = 100; }
48   
49  }
50  public class RandomInstanceClass4ProviderWithSRand : RandomInstanceProviderWithSRand {
51    public RandomInstanceClass4ProviderWithSRand() : base() { @class = 4; binWidth = binHeight = binDepth = 100; }
52   
53  }
54  public class RandomInstanceClass5ProviderWithSRand : RandomInstanceProviderWithSRand {
55    public RandomInstanceClass5ProviderWithSRand() : base() { @class = 5; binWidth = binHeight = binDepth = 100; }
56   
57  }
58
59  public class RandomInstanceClass6ProviderWithSRand : RandomInstanceProviderWithSRand {
60    public RandomInstanceClass6ProviderWithSRand() : base() {
61      @class = 6;
62      binWidth = binHeight = binDepth = 10;
63    }
64    protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
65      w = rand.Next(1, 10);
66      h = rand.Next(1, 10);
67      d = rand.Next(1, 10);
68    }
69  }
70  public class RandomInstanceClass7ProviderWithSRand : RandomInstanceProviderWithSRand {
71    public RandomInstanceClass7ProviderWithSRand() : base() {
72      @class = 7;
73      binWidth = binHeight = binDepth = 40;
74    }
75    protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
76      w = rand.Next(1, 35);
77      h = rand.Next(1, 35);
78      d = rand.Next(1, 35);
79    }
80  }
81  public class RandomInstanceClass8ProviderWithSRand : RandomInstanceProviderWithSRand {
82    public RandomInstanceClass8ProviderWithSRand() : base() {
83      @class = 8;
84      binWidth = binHeight = binDepth = 100;
85    }
86    protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
87      w = rand.Next(1, 100);
88      h = rand.Next(1, 100);
89      d = rand.Next(1, 100);
90    }
91  }
92
93  // class 9 from the paper (all-fill) is not implemented
94
95
96  public abstract class RandomInstanceProviderWithSRand : ProblemInstanceProvider<BPPData>, IProblemInstanceProvider<BPPData> {
97
98    /// <summary>
99    /// Number of created test items. This items are used for packing them into the bin
100    /// </summary>
101    private static readonly int[] numberOfGeneratedTestItems = new int[] { 10, 15, 20, 25, 30, 35, 40, 45, 50, 60, 70, 80, 90, 100, 150, 200 };   
102
103    /// <summary>
104    /// Number of instance for which should be created for each instance
105    /// </summary>
106    private static readonly int numberOfGeneratedInstances = 30;
107
108    #region Random Generator srand48
109    protected class SRand48 : Item, IRandom {
110      private object locker = new object();
111
112      private bool init = false;
113
114      private uint _h48;
115      private uint _l48;
116
117      public SRand48() {
118        if (!init) {
119          Seed((uint)DateTime.Now.Ticks);
120          init = true;
121        }
122      }
123      public SRand48(uint seed) {
124        if (!init) {
125          Seed(seed);
126          init = true;
127        }
128      }
129
130      public override IDeepCloneable Clone(Cloner cloner) {
131        throw new NotImplementedException();
132      }
133
134      public int Next() {
135        lock (locker) {
136          return (int)LRand48x();
137        }
138      }
139
140      public int Next(int maxVal) {
141        lock (locker) {
142          if (maxVal <= 0)
143            throw new ArgumentException("The interval [0, " + maxVal + ") is empty");
144          return (int)(LRand48x() % maxVal);
145        }
146      }
147
148      public int Next(int minVal, int maxVal) {
149        lock (locker) {
150          if (maxVal <= minVal)
151            throw new ArgumentException("The interval [" + minVal + ", " + maxVal + ") is empty");
152          return Next(maxVal - minVal + 1) + minVal;
153        }
154      }
155
156      public double NextDouble() {
157        lock (locker) {
158          return ((double)Next()) * (1.0 / 4294967296.0);
159        }
160      }
161
162      public void Reset() {
163        lock (locker) {
164          Seed((uint)DateTime.Now.Ticks);
165        }
166      }
167
168      public void Reset(int seed) {
169        lock (locker) {
170          Seed((uint)seed);
171        }
172      }
173
174      private void Seed(uint seed) {
175        _h48 = seed;
176        _l48 = 0x330E;
177      }
178
179      private int LRand48x() {
180        _h48 = (_h48 * 0xDEECE66D) + (_l48 * 0x5DEEC);
181        _l48 = _l48 * 0xE66D + 0xB;
182        _h48 = _h48 + (_l48 >> 16);
183        _l48 = _l48 & 0xFFFF;
184        return (int)(_h48 >> 1);
185      }
186
187    }
188
189    #endregion
190
191    protected int @class;
192    protected int binWidth, binHeight, binDepth;
193
194    #region Common information for displaying it on the ui
195   
196    public override string Name {
197      get { return string.Format("Martello, Pisinger, Vigo (class={0})", @class); }
198    }
199
200    public override string Description {
201      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."; }
202    }
203
204    public override Uri WebLink {
205      get { return null; }
206    }
207
208    public override string ReferencePublication {
209      get { return "Martello, Pisinger, Vigo: 'The Three-Dimensional Bin Packing Problem', Operations Research Vol 48, Issue 2, 2000, pp. 256-267."; }
210    }
211
212    #endregion
213    public RandomInstanceProviderWithSRand() : base() { }
214
215   
216    /// <summary>
217    /// Returns a collection of data descriptors. Each descriptor contains the seed for the random generator.
218    /// </summary>
219    /// <returns></returns>
220    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
221      // 10 classes
222      foreach (int numItems in numberOfGeneratedTestItems) {
223        for (int instance = 1; instance <= numberOfGeneratedInstances; instance++) {
224          string name = string.Format("n={0}-id={1:00} (class={2})", numItems, instance, @class);
225          /* As in the test programm of Silvano Martello, David Pisinger, Daniele Vigo given,
226           * the seed of the instance provider will be calculated by adding the number of generated items and teh instance number.
227           * This guarantees that the instances will always be the same
228           */
229          yield return new RandomDataDescriptor(name, name, numItems, @class, seed: numItems + instance);
230        }
231      }
232    }
233
234   
235    public override BPPData LoadData(IDataDescriptor dd) {
236      var randDd = dd as RandomDataDescriptor;
237      if (randDd == null)
238        throw new NotSupportedException("Cannot load data descriptor " + dd);
239
240      var data = new BPPData() {
241        BinShape = new PackingShape(binWidth, binHeight, binDepth),
242        Items = new PackingItem[randDd.NumItems]
243      };
244      var instanceRand = new SRand48((uint)randDd.Seed);
245      for (int i = 0; i < randDd.NumItems; i++) {
246        int w, h, d;
247        SampleItemParameters(instanceRand, out w, out h, out d);
248        data.Items[i] = new PackingItem(w, h, d, data.BinShape);
249      }
250      return data;
251    }
252
253   
254    /// <summary>
255    /// Generates the dimensions for a item by using the given random generator
256    /// </summary>
257    /// <param name="rand">Given random generator</param>
258    /// <param name="w">Calculated width of the item</param>
259    /// <param name="h">Calculated height of the item</param>
260    /// <param name="d">Calculated depth of the item</param>
261    protected virtual void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
262      Contract.Assert(@class >= 1 && @class <= 5);
263      /*var weights = new double[] { 0.1, 0.1, 0.1, 0.1, 0.1 };
264      weights[@class - 1] = 0.6;
265      var type = Enumerable.Range(1, 5).SampleProportional(rand, 1, weights).First();
266      */
267
268      // as by Martello and Vigo
269      int type = @class;
270      if (type <= 5) {
271        var t = rand.Next(1, 10);
272        if (t <= 5) {
273          type = t;
274        }
275      }
276
277      switch (type) {
278        case 1:
279          CreateInstanceDimensionsType1(rand, out w, out h, out d);
280          break;
281        case 2:
282          CreateInstanceDimensionsType2(rand, out w, out h, out d);
283          break;
284        case 3:
285          CreateInstanceDimensionsType3(rand, out w, out h, out d);
286          break;
287        case 4:
288          CreateInstanceDimensionsType4(rand, out w, out h, out d);
289          break;
290        case 5:
291          CreateInstanceDimensionsType5(rand, out w, out h, out d);
292          break;
293        default:
294            throw new InvalidProgramException();
295      }
296    }
297
298   
299    #region Instance dimensions generators for type 1 - 5
300    private void CreateInstanceDimensionsType1(IRandom rand, out int w, out int h, out int d) {
301      w = rand.Next(1, binWidth / 2);
302      h = rand.Next((binHeight * 2) / 3, binHeight);
303      d = rand.Next((binDepth * 2) / 3, binDepth);
304    }
305
306    private void CreateInstanceDimensionsType2(IRandom rand, out int w, out int h, out int d) {
307      w = rand.Next(((binWidth * 2) / 3), binWidth);
308      h = rand.Next(1, binHeight / 2);
309      d = rand.Next(((binDepth * 2) / 3), binDepth);
310    }
311
312    private void CreateInstanceDimensionsType3(IRandom rand, out int w, out int h, out int d) {
313      w = rand.Next(((binWidth * 2) / 3), binWidth);
314      h = rand.Next(((binHeight * 2) / 3), binHeight);
315      d = rand.Next(1, binDepth / 2);
316    }
317    private void CreateInstanceDimensionsType4(IRandom rand, out int w, out int h, out int d) {
318      w = rand.Next(binWidth / 2, binWidth);
319      h = rand.Next(binHeight / 2, binHeight);
320      d = rand.Next(binDepth / 2, binDepth);
321    }
322    private void CreateInstanceDimensionsType5(IRandom rand, out int w, out int h, out int d) {
323      w = rand.Next(1, binWidth / 2);
324      h = rand.Next(1, binHeight / 2);
325      d = rand.Next(1, binDepth / 2);
326    }
327   
328    #endregion
329
330
331
332    public override bool CanImportData {
333      get { return false; }
334    }
335    public override BPPData ImportData(string path) {
336      throw new NotSupportedException();
337    }
338
339    public override bool CanExportData {
340      get { return true; }
341    }
342
343    public override void ExportData(BPPData instance, string file) {
344      using (Stream stream = new FileStream(file, FileMode.OpenOrCreate, FileAccess.Write)) {
345        Export(instance, stream);
346      }
347    }
348    public static void Export(BPPData instance, Stream stream) {
349
350      using (var writer = new StreamWriter(stream)) {
351        writer.WriteLine(String.Format("{0,-5} {1,-5} {2,-5}   WBIN,HBIN,DBIN", instance.BinShape.Width, instance.BinShape.Height, instance.BinShape.Depth));
352        for (int i = 0; i < instance.NumItems; i++) {
353          if (i == 0)
354            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);
355          else
356            writer.WriteLine("{0,-5} {1,-5} {2,-5}", instance.Items[i].Width, instance.Items[i].Height, instance.Items[i].Depth);
357        }
358        writer.Flush();
359      }
360    }
361  }
362}
Note: See TracBrowser for help on using the repository browser.