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

Last change on this file since 15617 was 15617, checked in by rhanghof, 21 months ago

#2817:

  • The items can be rotated and tilted now.
  • Added pruning of extreme points in packed bins.
  • Added new packer which packs items by positioning them on the point with the minimum of wasted space. He uses rotating and tilting of items.
  • Added classes for sorting given items.
File size: 11.3 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2018 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
22using System;
23using System.Collections.Generic;
24using System.Diagnostics.Contracts;
25using System.IO;
26using System.Linq;
27using System.Reflection;
28using HeuristicLab.Common;
29using HeuristicLab.Core;
30using HeuristicLab.Problems.Instances;
31using HeuristicLab.Random;
32using HeuristicLab.Problems.BinPacking.Random;
33
34namespace HeuristicLab.Problems.BinPacking3D.Instances {
35  // make sure that for each class we have a separate entry in the problem instance providers
36
37  public class RandomInstanceClass1Provider : RandomInstanceProvider {
38    public RandomInstanceClass1Provider() : base(new SRand48()) { @class = 1; binWidth = binHeight = binDepth = 100; }
39
40  }
41
42  public class RandomInstanceClass2Provider : RandomInstanceProvider {
43    public RandomInstanceClass2Provider() : base(new SRand48()) { @class = 2; binWidth = binHeight = binDepth = 100; }
44
45  }
46  public class RandomInstanceClass3Provider : RandomInstanceProvider {
47    public RandomInstanceClass3Provider() : base(new SRand48()) { @class = 3; binWidth = binHeight = binDepth = 100; }
48
49  }
50  public class RandomInstanceClass4Provider : RandomInstanceProvider {
51    public RandomInstanceClass4Provider() : base(new SRand48()) { @class = 4; binWidth = binHeight = binDepth = 100; }
52
53  }
54  public class RandomInstanceClass5Provider : RandomInstanceProvider {
55    public RandomInstanceClass5Provider() : base(new SRand48()) { @class = 5; binWidth = binHeight = binDepth = 100; }
56
57  }
58
59  public class RandomInstanceClass6Provider : RandomInstanceProvider {
60    public RandomInstanceClass6Provider() : base(new SRand48()) {
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 RandomInstanceClass7Provider : RandomInstanceProvider {
71    public RandomInstanceClass7Provider() : base(new SRand48()) {
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 RandomInstanceClass8Provider : RandomInstanceProvider {
82    public RandomInstanceClass8Provider() : base(new SRand48()) {
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 RandomInstanceProvider : 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 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 readonly int _numberOfGeneratedInstances;
107
108    /// <summary>
109    /// Random generator for creating random packing items.
110    /// </summary>
111    private readonly IRandom _randomGenerator;
112
113
114    protected int @class;
115    protected int binWidth, binHeight, binDepth;
116
117    #region Common information for displaying on the ui
118
119    public override string Name {
120      get { return string.Format("Martello, Pisinger, Vigo (class={0})", @class); }
121    }
122
123    public override string Description {
124      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."; }
125    }
126
127    public override Uri WebLink {
128      get { return null; }
129    }
130
131    public override string ReferencePublication {
132      get { return "Martello, Pisinger, Vigo: 'The Three-Dimensional Bin Packing Problem', Operations Research Vol 48, Issue 2, 2000, pp. 256-267."; }
133    }
134
135    #endregion
136
137
138    public RandomInstanceProvider(IRandom randomGenerator, int numberOfGeneratedInstances = 10, int[] numberOfGeneratedTestItems = null) : base() {
139      _numberOfGeneratedInstances = numberOfGeneratedInstances;
140      if (numberOfGeneratedTestItems != null) {
141        _numberOfGeneratedTestItems = numberOfGeneratedTestItems;
142      }
143      _randomGenerator = randomGenerator;
144    }
145
146
147    /// <summary>
148    /// Returns a collection of data descriptors. Each descriptor contains the seed for the random generator.
149    /// </summary>
150    /// <returns></returns>
151    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
152      // 10 classes
153      foreach (int numItems in _numberOfGeneratedTestItems) {
154        for (int instance = 1; instance <= _numberOfGeneratedInstances; instance++) {
155          string name = string.Format("n={0}-id={1:00} (class={2})", numItems, instance, @class);
156          /* As in the test programm of Silvano Martello, David Pisinger, Daniele Vigo given,
157           * the seed of the instance provider will be calculated by adding the number of generated items and teh instance number.
158           * This guarantees that the instances will always be the same
159           */
160          yield return new RandomDataDescriptor(name, name, numItems, @class, seed: numItems + instance);
161        }
162      }
163    }
164
165    /// <summary>
166    /// Loads the data from the given data descriptor.
167    /// It retuns a bin packing problem data instance with the data of the random instance provider.
168    /// </summary>
169    /// <param name="dd"></param>
170    /// <returns></returns>
171    public override BPPData LoadData(IDataDescriptor dd) {
172      var randDd = dd as RandomDataDescriptor;
173      if (randDd == null) {
174        throw new NotSupportedException("Cannot load data descriptor " + dd);
175      }
176
177      var data = new BPPData() {
178        BinShape = new PackingShape(binWidth, binHeight, binDepth),
179        Items = new PackingItem[randDd.NumItems]
180      };
181      _randomGenerator.Reset(randDd.Seed);
182      for (int i = 0; i < randDd.NumItems; i++) {
183        int w, h, d;
184        SampleItemParameters(_randomGenerator, out w, out h, out d);
185        data.Items[i] = new PackingItem(w, h, d, data.BinShape);
186      }
187      return data;
188    }
189
190
191    /// <summary>
192    /// Generates the dimensions for a item by using the given random generator
193    /// </summary>
194    /// <param name="rand">Given random generator</param>
195    /// <param name="w">Calculated width of the item</param>
196    /// <param name="h">Calculated height of the item</param>
197    /// <param name="d">Calculated depth of the item</param>
198    protected virtual void SampleItemParameters(IRandom rand, out int w, out int h, out int d) {
199      Contract.Assert(@class >= 1 && @class <= 5);
200      /*var weights = new double[] { 0.1, 0.1, 0.1, 0.1, 0.1 };
201      weights[@class - 1] = 0.6;
202      var type = Enumerable.Range(1, 5).SampleProportional(rand, 1, weights).First();
203      */
204
205      // as by Martello and Vigo
206      int type = @class;
207      if (type <= 5) {
208        var t = rand.Next(1, 10);
209        if (t <= 5) {
210          type = t;
211        }
212      }
213
214      switch (type) {
215        case 1:
216          CreateInstanceDimensionsType1(rand, out w, out h, out d);
217          break;
218        case 2:
219          CreateInstanceDimensionsType2(rand, out w, out h, out d);
220          break;
221        case 3:
222          CreateInstanceDimensionsType3(rand, out w, out h, out d);
223          break;
224        case 4:
225          CreateInstanceDimensionsType4(rand, out w, out h, out d);
226          break;
227        case 5:
228          CreateInstanceDimensionsType5(rand, out w, out h, out d);
229          break;
230        default:
231          throw new InvalidProgramException();
232      }
233    }
234
235
236    #region Instance dimensions generators for type 1 - 5
237    private void CreateInstanceDimensionsType1(IRandom rand, out int w, out int h, out int d) {
238      w = rand.Next(1, binWidth / 2);
239      h = rand.Next((binHeight * 2) / 3, binHeight);
240      d = rand.Next((binDepth * 2) / 3, binDepth);
241    }
242
243    private void CreateInstanceDimensionsType2(IRandom rand, out int w, out int h, out int d) {
244      w = rand.Next(((binWidth * 2) / 3), binWidth);
245      h = rand.Next(1, binHeight / 2);
246      d = rand.Next(((binDepth * 2) / 3), binDepth);
247    }
248
249    private void CreateInstanceDimensionsType3(IRandom rand, out int w, out int h, out int d) {
250      w = rand.Next(((binWidth * 2) / 3), binWidth);
251      h = rand.Next(((binHeight * 2) / 3), binHeight);
252      d = rand.Next(1, binDepth / 2);
253    }
254    private void CreateInstanceDimensionsType4(IRandom rand, out int w, out int h, out int d) {
255      w = rand.Next(binWidth / 2, binWidth);
256      h = rand.Next(binHeight / 2, binHeight);
257      d = rand.Next(binDepth / 2, binDepth);
258    }
259    private void CreateInstanceDimensionsType5(IRandom rand, out int w, out int h, out int d) {
260      w = rand.Next(1, binWidth / 2);
261      h = rand.Next(1, binHeight / 2);
262      d = rand.Next(1, binDepth / 2);
263    }
264
265    #endregion
266
267
268
269    public override bool CanImportData {
270      get { return false; }
271    }
272    public override BPPData ImportData(string path) {
273      throw new NotSupportedException();
274    }
275
276    public override bool CanExportData {
277      get { return true; }
278    }
279
280    public override void ExportData(BPPData instance, string file) {
281      using (Stream stream = new FileStream(file, FileMode.OpenOrCreate, FileAccess.Write)) {
282        Export(instance, stream);
283      }
284    }
285    public static void Export(BPPData instance, Stream stream) {
286
287      using (var writer = new StreamWriter(stream)) {
288        writer.WriteLine(String.Format("{0,-5} {1,-5} {2,-5}   WBIN,HBIN,DBIN", instance.BinShape.Width, instance.BinShape.Height, instance.BinShape.Depth));
289        for (int i = 0; i < instance.NumItems; i++) {
290          if (i == 0)
291            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);
292          else
293            writer.WriteLine("{0,-5} {1,-5} {2,-5}", instance.Items[i].Width, instance.Items[i].Height, instance.Items[i].Depth);
294        }
295        writer.Flush();
296      }
297    }
298  }
299}
Note: See TracBrowser for help on using the repository browser.