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

Last change on this file since 15473 was 15473, checked in by rhanghof, 22 months ago

#2817

  • Added unit tests
  • Refactoring of bp 3D
File size: 11.3 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;
33using HeuristicLab.Problems.BinPacking.Random;
34
35namespace HeuristicLab.Problems.BinPacking3D.Instances {
36  // make sure that for each class we have a separate entry in the problem instance providers
37
38  public class RandomInstanceClass1Provider : RandomInstanceProvider {
39    public RandomInstanceClass1Provider() : base(new SRand48()) { @class = 1; binWidth = binHeight = binDepth = 100; }
40
41  }
42
43  public class RandomInstanceClass2Provider : RandomInstanceProvider {
44    public RandomInstanceClass2Provider() : base(new SRand48()) { @class = 2; binWidth = binHeight = binDepth = 100; }
45
46  }
47  public class RandomInstanceClass3Provider : RandomInstanceProvider {
48    public RandomInstanceClass3Provider() : base(new SRand48()) { @class = 3; binWidth = binHeight = binDepth = 100; }
49
50  }
51  public class RandomInstanceClass4Provider : RandomInstanceProvider {
52    public RandomInstanceClass4Provider() : base(new SRand48()) { @class = 4; binWidth = binHeight = binDepth = 100; }
53
54  }
55  public class RandomInstanceClass5Provider : RandomInstanceProvider {
56    public RandomInstanceClass5Provider() : base(new SRand48()) { @class = 5; binWidth = binHeight = binDepth = 100; }
57
58  }
59
60  public class RandomInstanceClass6Provider : RandomInstanceProvider {
61    public RandomInstanceClass6Provider() : base(new SRand48()) {
62      @class = 6;
63      binWidth = binHeight = binDepth = 10;
64    }
65    protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
66      w = rand.Next(1, 10);
67      h = rand.Next(1, 10);
68      d = rand.Next(1, 10);
69    }
70  }
71  public class RandomInstanceClass7Provider : RandomInstanceProvider {
72    public RandomInstanceClass7Provider() : base(new SRand48()) {
73      @class = 7;
74      binWidth = binHeight = binDepth = 40;
75    }
76    protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
77      w = rand.Next(1, 35);
78      h = rand.Next(1, 35);
79      d = rand.Next(1, 35);
80    }
81  }
82  public class RandomInstanceClass8Provider : RandomInstanceProvider {
83    public RandomInstanceClass8Provider() : base(new SRand48()) {
84      @class = 8;
85      binWidth = binHeight = binDepth = 100;
86    }
87    protected override void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
88      w = rand.Next(1, 100);
89      h = rand.Next(1, 100);
90      d = rand.Next(1, 100);
91    }
92  }
93
94  // class 9 from the paper (all-fill) is not implemented
95
96
97  public abstract class RandomInstanceProvider : ProblemInstanceProvider<BPPData>, IProblemInstanceProvider<BPPData> {
98
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;
113
114
115    protected int @class;
116    protected int binWidth, binHeight, binDepth;
117
118    #region Common information for displaying on the ui
119
120    public override string Name {
121      get { return string.Format("Martello, Pisinger, Vigo (class={0})", @class); }
122    }
123
124    public override string Description {
125      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."; }
126    }
127
128    public override Uri WebLink {
129      get { return null; }
130    }
131
132    public override string ReferencePublication {
133      get { return "Martello, Pisinger, Vigo: 'The Three-Dimensional Bin Packing Problem', Operations Research Vol 48, Issue 2, 2000, pp. 256-267."; }
134    }
135
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>
152    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
153      // 10 classes
154      foreach (int numItems in _numberOfGeneratedTestItems) {
155        for (int instance = 1; instance <= _numberOfGeneratedInstances; instance++) {
156          string name = string.Format("n={0}-id={1:00} (class={2})", numItems, instance, @class);
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);
162        }
163      }
164    }
165
166    /// <summary>
167    /// Loads the data from the given data descriptor.
168    /// It retuns a bin packing problem data instance with the data of the random instance provider.
169    /// </summary>
170    /// <param name="dd"></param>
171    /// <returns></returns>
172    public override BPPData LoadData(IDataDescriptor dd) {
173      var randDd = dd as RandomDataDescriptor;
174      if (randDd == null) {
175        throw new NotSupportedException("Cannot load data descriptor " + dd);
176      }
177
178      var data = new BPPData() {
179        BinShape = new PackingShape(binWidth, binHeight, binDepth),
180        Items = new PackingItem[randDd.NumItems]
181      };
182      _randomGenerator.Reset(randDd.Seed);
183      for (int i = 0; i < randDd.NumItems; i++) {
184        int w, h, d;
185        SampleItemParameters(_randomGenerator, out w, out h, out d);
186        data.Items[i] = new PackingItem(w, h, d, data.BinShape);
187      }
188      return data;
189    }
190
191
192    /// <summary>
193    /// Generates the dimensions for a item by using the given random generator
194    /// </summary>
195    /// <param name="rand">Given random generator</param>
196    /// <param name="w">Calculated width of the item</param>
197    /// <param name="h">Calculated height of the item</param>
198    /// <param name="d">Calculated depth of the item</param>
199    protected virtual void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
200      Contract.Assert(@class >= 1 && @class <= 5);
201      /*var weights = new double[] { 0.1, 0.1, 0.1, 0.1, 0.1 };
202      weights[@class - 1] = 0.6;
203      var type = Enumerable.Range(1, 5).SampleProportional(rand, 1, weights).First();
204      */
205
206      // as by Martello and Vigo
207      int type = @class;
208      if (type <= 5) {
209        var t = rand.Next(1, 10);
210        if (t <= 5) {
211          type = t;
212        }
213      }
214
215      switch (type) {
216        case 1:
217          CreateInstanceDimensionsType1(rand, out w, out h, out d);
218          break;
219        case 2:
220          CreateInstanceDimensionsType2(rand, out w, out h, out d);
221          break;
222        case 3:
223          CreateInstanceDimensionsType3(rand, out w, out h, out d);
224          break;
225        case 4:
226          CreateInstanceDimensionsType4(rand, out w, out h, out d);
227          break;
228        case 5:
229          CreateInstanceDimensionsType5(rand, out w, out h, out d);
230          break;
231        default:
232          throw new InvalidProgramException();
233      }
234    }
235
236
237    #region Instance dimensions generators for type 1 - 5
238    private void CreateInstanceDimensionsType1(IRandom rand, out int w, out int h, out int d) {
239      w = rand.Next(1, binWidth / 2);
240      h = rand.Next((binHeight * 2) / 3, binHeight);
241      d = rand.Next((binDepth * 2) / 3, binDepth);
242    }
243
244    private void CreateInstanceDimensionsType2(IRandom rand, out int w, out int h, out int d) {
245      w = rand.Next(((binWidth * 2) / 3), binWidth);
246      h = rand.Next(1, binHeight / 2);
247      d = rand.Next(((binDepth * 2) / 3), binDepth);
248    }
249
250    private void CreateInstanceDimensionsType3(IRandom rand, out int w, out int h, out int d) {
251      w = rand.Next(((binWidth * 2) / 3), binWidth);
252      h = rand.Next(((binHeight * 2) / 3), binHeight);
253      d = rand.Next(1, binDepth / 2);
254    }
255    private void CreateInstanceDimensionsType4(IRandom rand, out int w, out int h, out int d) {
256      w = rand.Next(binWidth / 2, binWidth);
257      h = rand.Next(binHeight / 2, binHeight);
258      d = rand.Next(binDepth / 2, binDepth);
259    }
260    private void CreateInstanceDimensionsType5(IRandom rand, out int w, out int h, out int d) {
261      w = rand.Next(1, binWidth / 2);
262      h = rand.Next(1, binHeight / 2);
263      d = rand.Next(1, binDepth / 2);
264    }
265
266    #endregion
267
268
269
270    public override bool CanImportData {
271      get { return false; }
272    }
273    public override BPPData ImportData(string path) {
274      throw new NotSupportedException();
275    }
276
277    public override bool CanExportData {
278      get { return true; }
279    }
280
281    public override void ExportData(BPPData instance, string file) {
282      using (Stream stream = new FileStream(file, FileMode.OpenOrCreate, FileAccess.Write)) {
283        Export(instance, stream);
284      }
285    }
286    public static void Export(BPPData instance, Stream stream) {
287
288      using (var writer = new StreamWriter(stream)) {
289        writer.WriteLine(String.Format("{0,-5} {1,-5} {2,-5}   WBIN,HBIN,DBIN", instance.BinShape.Width, instance.BinShape.Height, instance.BinShape.Depth));
290        for (int i = 0; i < instance.NumItems; i++) {
291          if (i == 0)
292            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);
293          else
294            writer.WriteLine("{0,-5} {1,-5} {2,-5}", instance.Items[i].Width, instance.Items[i].Height, instance.Items[i].Depth);
295        }
296        writer.Flush();
297      }
298    }
299  }
300}
Note: See TracBrowser for help on using the repository browser.