Free cookie consent management tool by TermsFeed Policy Generator

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

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

#2817:

  • New RandomInstanceProvider added for testing the EP-algorithm with the same instances as Silvano Martello, David Pisinger, Daniele Vigo in their paper.
  • Added some Unit Tests for the BinPacking-3D EP-algorithm
File size: 11.1 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 HeuristicLab.Common;
29using HeuristicLab.Core;
30using HeuristicLab.Problems.Instances;
31using HeuristicLab.Random;
32
33namespace HeuristicLab.Problems.BinPacking3D {
34  // make sure that for each class we have a separate entry in the problem instance providers
35  public class RandomInstanceClass1ProviderWithSRand : RandomInstanceProviderWithSRand {
36    public RandomInstanceClass1ProviderWithSRand() : base() { @class = 1; binWidth = binHeight = binDepth = 100; }
37  }
38  public class RandomInstanceClass2ProviderWithSRand : RandomInstanceProviderWithSRand {
39    public RandomInstanceClass2ProviderWithSRand() : base() { @class = 2; binWidth = binHeight = binDepth = 100; }
40  }
41  public class RandomInstanceClass3ProviderWithSRand : RandomInstanceProviderWithSRand {
42    public RandomInstanceClass3ProviderWithSRand() : base() { @class = 3; binWidth = binHeight = binDepth = 100; }
43  }
44  public class RandomInstanceClass4ProviderWithSRand : RandomInstanceProviderWithSRand {
45    public RandomInstanceClass4ProviderWithSRand() : base() { @class = 4; binWidth = binHeight = binDepth = 100; }
46  }
47  public class RandomInstanceClass5ProviderWithSRand : RandomInstanceProviderWithSRand {
48    public RandomInstanceClass5ProviderWithSRand() : base() { @class = 5; binWidth = binHeight = binDepth = 100; }
49  }
50
51  public class RandomInstanceClass6ProviderWithSRand : RandomInstanceProviderWithSRand {
52    public RandomInstanceClass6ProviderWithSRand() : base() {
53      @class = 6;
54      binWidth = binHeight = binDepth = 10;
55    }
56    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);
60    }
61  }
62  public class RandomInstanceClass7ProviderWithSRand : RandomInstanceProviderWithSRand {
63    public RandomInstanceClass7ProviderWithSRand() : base() {
64      @class = 7;
65      binWidth = binHeight = binDepth = 40;
66    }
67    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);
71    }
72  }
73  public class RandomInstanceClass8ProviderWithSRand : RandomInstanceProviderWithSRand {
74    public RandomInstanceClass8ProviderWithSRand() : base() {
75      @class = 8;
76      binWidth = binHeight = binDepth = 100;
77    }
78    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);
82    }
83  }
84
85  // class 9 from the paper (all-fill) is not implemented
86
87
88  public abstract class RandomInstanceProviderWithSRand : ProblemInstanceProvider<BPPData>, IProblemInstanceProvider<BPPData> {
89    #region Random Generator srand48
90    protected class SRand48 : Item, IRandom {
91      private object locker = new object();
92
93      private bool init = false;
94
95      private uint _h48;
96      private uint _l48;
97
98      public SRand48() {
99        if (!init) {
100          Seed((uint)DateTime.Now.Ticks);
101          init = true;
102        }
103      }
104      public SRand48(uint seed) {
105        if (!init) {
106          Seed(seed);
107          init = true;
108        }
109      }
110
111      public override IDeepCloneable Clone(Cloner cloner) {
112        throw new NotImplementedException();
113      }
114
115      public int Next() {
116        lock (locker) {
117          return (int)LRand48x();
118        }
119      }
120
121      public int Next(int maxVal) {
122        lock (locker) {
123          if (maxVal <= 0)
124            throw new ArgumentException("The interval [0, " + maxVal + ") is empty");
125          return (int)(LRand48x() % maxVal);
126        }
127      }
128
129      public int Next(int minVal, int maxVal) {
130        lock (locker) {
131          if (maxVal <= minVal)
132            throw new ArgumentException("The interval [" + minVal + ", " + maxVal + ") is empty");
133          return Next(maxVal - minVal + 1) + minVal;
134        }
135      }
136
137      public double NextDouble() {
138        lock (locker) {
139          return ((double)Next()) * (1.0 / 4294967296.0);
140        }
141      }
142
143      public void Reset() {
144        lock (locker) {
145          Seed((uint)DateTime.Now.Ticks);
146        }
147      }
148
149      public void Reset(int seed) {
150        lock (locker) {
151          Seed((uint)seed);
152        }
153      }
154
155      private void Seed(uint seed) {
156        _h48 = seed;
157        _l48 = 0x330E;
158      }
159
160      private int LRand48x() {
161        _h48 = (_h48 * 0xDEECE66D) + (_l48 * 0x5DEEC);
162        _l48 = _l48 * 0xE66D + 0xB;
163        _h48 = _h48 + (_l48 >> 16);
164        _l48 = _l48 & 0xFFFF;
165        return (int)(_h48 >> 1);
166      }
167
168    }
169
170    #endregion
171
172    protected int @class;
173    protected int binWidth, binHeight, binDepth;
174
175    public override string Name {
176      get { return string.Format("Martello, Pisinger, Vigo (class={0})", @class); }
177    }
178
179    public override string Description {
180      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."; }
181    }
182
183    public override Uri WebLink {
184      get { return null; }
185    }
186
187    public override string ReferencePublication {
188      get { return "Martello, Pisinger, Vigo: 'The Three-Dimensional Bin Packing Problem', Operations Research Vol 48, Issue 2, 2000, pp. 256-267."; }
189    }
190
191    public RandomInstanceProviderWithSRand() : base() { }
192
193    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
194      // 10 classes
195      //var rand = new MersenneTwister(1234); // fixed seed to makes sure that instances are always the same
196      foreach (int numItems in new int[] { 10, 15, 20, 25, 30, 35, 40, 45, 50, 60, 70, 80, 90, 100, 150, 200 }) {
197        // get class parameters
198        // generate 30 different instances for each class
199        foreach (int instance in Enumerable.Range(1, 30)) {
200          var rand = new SRand48((uint)(numItems + instance));
201          string name = string.Format("n={0}-id={1:00} (class={2})", numItems, instance, @class);
202          var dd = new RandomDataDescriptor(name, name, numItems, @class, seed: rand.Next());
203          yield return dd;
204        }
205      }
206    }
207
208    public override BPPData LoadData(IDataDescriptor dd) {
209      var randDd = dd as RandomDataDescriptor;
210      if (randDd == null)
211        throw new NotSupportedException("Cannot load data descriptor " + dd);
212
213      var data = new BPPData() {
214        BinShape = new PackingShape(binWidth, binHeight, binDepth),
215        Items = new PackingItem[randDd.NumItems]
216      };
217      var instanceRand = new SRand48((uint)randDd.Seed);
218      for (int i = 0; i < randDd.NumItems; i++) {
219        int w, h, d;
220        SampleItemParameters(instanceRand, out w, out h, out d);
221        data.Items[i] = new PackingItem(w, h, d, data.BinShape);
222      }
223      return data;
224    }
225
226    // default implementation for class 1 .. 5
227    protected virtual void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
228      // for classes 1 - 5
229      Contract.Assert(@class >= 1 && @class <= 5);
230      var weights = new double[] { 0.1, 0.1, 0.1, 0.1, 0.1 };
231      weights[@class - 1] = 0.6;
232      var type = Enumerable.Range(1, 5).SampleProportional(rand, 1, weights).First();
233
234      int minW, maxW;
235      int minH, maxH;
236      int minD, maxD;
237      GetItemParameters(type, rand, binWidth, binHeight, binDepth,
238        out minW, out maxW, out minH, out maxH, out minD, out maxD);
239
240      w = rand.Next(minW, maxW + 1);
241      h = rand.Next(minH, maxH + 1);
242      d = rand.Next(minD, maxD + 1);
243    }
244
245    private void GetItemParameters(int type, IRandom rand,
246      int w, int h, int d,
247      out int minW, out int maxW, out int minH, out int maxH, out int minD, out int maxD) {
248      switch (type) {
249        case 1: {
250            minW = 1;
251            maxW = w / 2; // integer division on purpose (see paper)
252            minH = h * 2 / 3;
253            maxH = h;
254            minD = d * 2 / 3;
255            maxD = d;
256            break;
257          }
258        case 2: {
259            minW = w * 2 / 3;
260            maxW = w;
261            minH = 1;
262            maxH = h / 2;
263            minD = d * 2 / 3;
264            maxD = d;
265            break;
266          }
267        case 3: {
268            minW = w * 2 / 3;
269            maxW = w;
270            minH = h * 2 / 3;
271            maxH = h;
272            minD = 1;
273            maxD = d / 2;
274            break;
275          }
276        case 4: {
277            minW = w / 2;
278            maxW = w;
279            minH = h / 2;
280            maxH = h;
281            minD = d / 2;
282            maxD = d;
283            break;
284          }
285        case 5: {
286            minW = 1;
287            maxW = w / 2;
288            minH = 1;
289            maxH = h / 2;
290            minD = 1;
291            maxD = d / 2;
292            break;
293          }
294        default: {
295            throw new InvalidProgramException();
296          }
297      }
298    }
299
300    public override bool CanImportData {
301      get { return false; }
302    }
303    public override BPPData ImportData(string path) {
304      throw new NotSupportedException();
305    }
306
307    public override bool CanExportData {
308      get { return true; }
309    }
310
311    public override void ExportData(BPPData instance, string file) {
312      using (Stream stream = new FileStream(file, FileMode.OpenOrCreate, FileAccess.Write)) {
313        Export(instance, stream);
314      }
315    }
316    public static void Export(BPPData instance, Stream stream) {
317
318      using (var writer = new StreamWriter(stream)) {
319        writer.WriteLine(String.Format("{0,-5} {1,-5} {2,-5}   WBIN,HBIN,DBIN", instance.BinShape.Width, instance.BinShape.Height, instance.BinShape.Depth));
320        for (int i = 0; i < instance.NumItems; i++) {
321          if (i == 0)
322            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);
323          else
324            writer.WriteLine("{0,-5} {1,-5} {2,-5}", instance.Items[i].Width, instance.Items[i].Height, instance.Items[i].Depth);
325
326        }
327        writer.Flush();
328      }
329    }
330
331  }
332}
Note: See TracBrowser for help on using the repository browser.